Build source string from damaged string

Question

I was given a damaged line with spaces present in the wrong places, and a dictionary containing the correct words. The challenge is to build the original string using a dictionary.

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

I mean the recursive approach, since each character has two possibilities, this can be a new word or part of the previous word. Am I going in the right direction? Is there a better approach to this problem?

Answer 1

You must remove all spaces, then match the words in the dictionary with the line header and recursively check if the tail of the line can be matched in the same way. You want the recursive function to return all matches, like an array or a tree of strings that match. I just wrote it to output the output below, but you can save the 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 

Then you call printAllMatches("", stringWithoutSpaces) . When the front of stringWithoutSpaces , it switches to head .

Answer 2

Suppose 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, now we can find the answer, BUT what is Big (O)?

In addition, we have two positions to accelerate:

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

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

Now complexity is O (n * k)

Answer 3

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

Below is the C ++ code for it -

 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,ij))!=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]; } }