15.3. StringCoder - Part A¶
The following is a free response question from 2008. It was question 2 on the exam. You can see all the free response questions from past exams at https://apstudents.collegeboard.org/courses/ap-computer-science-a/free-response-questions-by-year.
Question 2. Consider a method of encoding and decoding words that is based on a master string. This master string
will contain all the letters of the alphabet, some possibly more than once. An example of a master string is
"sixtyzipperswerequicklypickedfromthewovenjutebag". This string and its indexes are
shown below.
Figure 1: An example string with indices¶
An encoded string is defined by a list of string parts. A string part is defined by its starting index in the
master string and its length. For example, the string "overeager" is encoded as the list of string parts
[ (37, 3), (14, 2), (46, 2), (9, 2) ] denoting the substrings "ove", "re", "ag", and "er".
String parts will be represented by the StringPart class shown below.
public class StringPart
{
/**
* @param start the starting position of the substring in a master string
* @param length the length of the substring in a master string
*/
public StringPart(int start, int length)
{
/* implementation not shown */
}
/**
* @return the starting position of the substring in a master string
*/
public int getStart()
{
/* implementation not shown */
}
/**
* @return the length of the substring in a master string
*/
public int getLength()
{
/* implementation not shown */
}
// There may be other instance variables, constructors, and methods
}
The class StringCoder provides methods to encode and decode words using a given master string. When
encoding, there may be multiple matching string parts of the master string. The helper method findPart is
provided to choose a string part within the master string that matches the beginning of a given string.
public class StringCoder
{
private String masterString;
/**
* @param master the master string for the StringCoder Precondition: the master
* string contains all the letters of the alphabet
*/
public StringCoder(String master)
{
masterString = master;
}
/**
* @param parts an ArrayList of string parts that are valid in the master
* string Precondition: parts.size() > 0
* @return the string obtained by concatenating the parts of the master string
*/
public String decodeString(ArrayList<StringPart> parts)
{
/* to be implemented in part (a) */
}
/**
* @param str the string to encode using the master string Precondition: all of
* the characters in str appear in the master string; str.length() > 0
* @return a string part in the master string that matches the beginning of
* str. The returned string part has length at least 1.
*/
private StringPart findPart(String str)
{
/* implementation not shown */
}
/**
* @param word the string to be encoded Precondition: all of the characters in
* word appear in the master string; word.length() > 0
* @return an ArrayList of string parts of the master string that can be
* combined to create word
*/
public ArrayList<StringPart> encodeString(String word)
{
/* to be implemented in part (b) */
}
// There may be other instance variables, constructors, and methods
}
15.3.1. Try and Solve It¶
Part a. Finish writing the StringCoder method decodeString. This method retrieves the substrings in the master
string represented by each of the StringPart objects in parts, concatenates them in the order in
which they appear in parts, and returns the result.
The code below contains a main method for testing the decodeString method.
Finish writing the StringCoder method decodeString.