Construct the original string from the corrupted string

Question

I have been given a corrupted string with spaces present at wrong places and a dictionary containing the correct words. The challenge is to construct the original string using the dictionary.

For example : 
Dictionary : ["how","are","you"]
Corrupted String : ho ware y ou
Original String : how are you

I am thinking of a recursive approach since every character there are 2 possibilities, it can be a new word or a part of the previous word. Am I going in the right direction? Is there a better approach for this problem?

Not recursive because u don't know the length and may go out of the stack. 1 remiove all the spaces. 2 go testing words against the head (beginsWith) and, when found, output word and remove word.lenght from the head — eduyayo, Apr 21 '15 at 05:44
Strip all spaces. Then, split the remaining letters according to the dictionary. In case of ambiguity, apply backtracking. — Ulrich Eckhardt, Apr 21 '15 at 05:44
Ulrich Eckhardt is right. You may end with no word to fit the last chars, should try the next fittest for previous iteration — eduyayo, Apr 21 '15 at 05:46
I think you can use dynamic programming when you want to implement recursive... — kaitian521, Apr 21 '15 at 06:06

Edward Doolittle · Accepted Answer · 2015-04-22T16:20:53.240

You should remove all the spaces, then match words in the dictionary with the head of the string and recursively check whether the tail of the string can be matched in the same manner. You want the recursive function to return all matches, e.g., an array or tree of strings that match. I've just written it to print output below, but you could store output instead.

printAllMatches(String head, String tail)
  if tail.equals("") print head and return
  for each word w in dictionary
    if w matches beginning of tail
      printAllMatches(head + " " + w, tail - w) // remove w from front of tail

You then call the function by printAllMatches("", stringWithoutSpaces). As the front of stringWithoutSpaces gets processed, it gets shifted over to head.

score 3 · Answer 2 · edited May 23 '17 at 12:22

Suppose that we just want to find one possible answer.

Recursion is a good method to use. LIKE this:

S = Corrupted String . replace(' ', '') // remove all [:space:]

def recursive(position):
  if position == len(S):                 // A
    return True     // we found a solution!

  for i in range(1, len(S) - position + 1):
    if S[position: poition + i] in Dictionary:      // B
      if recursive(position + i):
         return True
    else:
      break
   // Find nothing, just return False
   return False

recursive(0)

OK, we now can find a answer, BUT what is the Big(O)?

In addition, we have two positions to accelerate:

A. when we look up if a word is in a dictionary, we can use trie-tree(http://en.wikipedia.org/wiki/Trie) to speed up. So we avoid looking for it from Red-Black Tree every time

B. we should remember the calculated answer: dynamic programming is a good solution, since you use recursive now, you can use dynamic programming memoization [What is the difference between memoization and dynamic programming?

Now, the complexity is O(n*k)

score 0 · Answer 3 · answered Jun 28 '15 at 13:14

After removing spaces from the string we can use dynamic programming to check if we can break the string into words present in the dictionary.

Below is C++ code for the same -

void printOriginalString(string s, unordered_set<string> &dict)
{
    int len = s.size();
    bool res[len+1];
    fill(res,res+len,0);
    int i,j;
    res[0] = true;

    for(i=1;i<=len;i++)
    {
        for(j=0;j<i;j++)
        {
            res[i] = res[j] && (dict.find(s.substr(j,i-j))!=dict.end()); //if both prefix and suffix present in dictionary
            if(res[i]) //found the word
                break;
        }
    }
    for(i=0;i<len;i++) //print the original string
    {
       if(res[i])
          cout<<" ";

       cout<<str[i];
    }

}

Construct the original string from the corrupted string

3 Answers3