AutoFix

TCCC '04 Semifinals 3 · 2004-02-23 · by lars2520

TCCC '04 Semifinals 3 · 2004-02-23 · by lars2520 · String Manipulation

Show categories

Class Name: AutoFix

Return Type: String

Method Name: fix

Arg Types: (string, vector<int>, vector<string>)

Problem Statement

Modern word processors often auto-correct certain commonly occurring typos. For example, if you type in "teh" it might be automatically corrected to "the". Sometimes, this can be annoying if you really want to type "teh" (perhaps it is an acronym). In this problem we are going to correct a specific kind of typing error. We will be looking for instances where someone types in two words (a word is a sequence of letters that is surrounded on both sides by a space and/or the edge of the String) as "xxxxx xyyyyy", when they meant "xxxxxx yyyyy". Here, "xxxxxx" and "yyyyy" represent two words in our dictionary. For example, if someone types in "th eproblem", we might correct it to "the problem". But, to avoid the annoying situation mentioned above, we will only make the correction when the last letter of the first word is typed 20 milliseconds or less after the preceding space. In other words, we want to make the correction only when a person almost types the characters in the right order, but his timing is just a little off. Furthermore, we only want to make the correction if at least one of the two words is not already in our dictionary, and both of the words after the transformation are in our dictionary. Thus, for example, if "th" and "eproblem" were both in the dictionary as valid words, we would not make the transformation, even if "the" and "problem" were also in the dictionary.

You will be given a String, sentence, representing the characters typed. You will also be given a int[], times representing the times (in milliseconds) since the start of typing that each key was pressed. Each character in sentence corresponds to the element of times with the same index. You will also be given a String[], dictionary, which represents a list of words (all in lowercase). Your task is to make the transformation mentioned above, ignoring the case of the characters in sentence, and starting from the beginning of sentence and moving forward. Though you should ignore case in determining whether or not to make the transformation, you should still preserve the cases of the letters in sentence (see examples). You should change the sentence as you go, and do so in one pass from left to right (see examples 4 and 5).

Notes

The words in dictionary are all lowercase, but applying the transformation should be done without regard to case (see examples)

Constraints

dictionary will contain between 1 and 50 elements, inclusive.
Each element of dictionary will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive.
sentence will contain between 1 and 50 characters, inclusive.
Each character of sentence will be a letter ('a'-'z' or 'A'-'Z') or a space (' ').
There will be no leading, trailing, or double spaces in sentence.
times will contain the same number of elements as sentence has characters.
Each element of times will be between 0 and 1,000,000, inclusive.
times will be sorted in strictly ascending order.

Examples

"Th EProblem"
{5,46,55,75,101,130,453,531,692,780,1003}
{"the","problem","th"}
Returns: "ThE Problem"

The space is typed after 55 milliseconds, while the 'e' is typed after 75. Since these are within 20 milliseconds of each other, they may be swapped.

"TH EPROBLEM"
{5,46,55,99,101,130,453,531,692,780,1003}
{"the","problem"}
Returns: "TH EPROBLEM"

Here the 'E' is typed 44 milliseconds after the space and hence may not be swapped.

"TH Eproblem"
{5,46,55,59,101,130,453,531,692,780,1003}
{"the","problem","th","eproblem"}
Returns: "TH Eproblem"

Though the 'E' and the space are typed within 20 milliseconds of each other, both "th" and "eproblem" are in the dictionary, so no swap occurs.

"onc eupo n atime"
{10,20,30,40,50,60,70,80,90,100,
 110,120,130,140,150,160}
{"once","upon","a","time"}
Returns: "onc eupo n atime"

Note that if we applied the transformation at all of the spaces, we would end up with 4 valid words, but our algorithm only does one pair at a time, and hence can do nothing here.

"Th eQuic kBrown Fox JUMPE Dover"
{10,20,30,40,50,60,70,80,90,100,
 110,120,130,140,150,160,170,180,
 280,380,480,580,680,780,880,980,
 1080,1180,1280,1380,1480}
{"the","quick","brown","fox","quic","jumped","over","ox","jump"}
Returns: "The Quick Brown Fox JUMPE Dover"

Originally, we can't swap the space and the 'k' to form "eQuick", because that is not in the dictionary. However, since we are working from left to right, and changing the sentence as we go, we move the 'e' to form "The", (as "quic" is in the dictionary) and then when we look at the 'k', we are allowed to move it.

"a bbb aab a b"
{1,2,3,4,5,6,7,8,9,10,11,12,13}
{"ab","bba","bbba"}
Returns: "a bbba ab a b"

Notice that, after we apply the transformation between the second and third words, if we started over we would apply the transformation between the first and second words. However, we are applying transformations in one pass, from left to right, so we don't go back and do this.

Submissions are judged against all 59 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AutoFix with a public method string fix(string sentence, vector<int> times, vector<string> dictionary) · 59 test cases · 2 s / 256 MB per case