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?

Answer 1

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.

Answer 2

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)