Konstruieren Sie die ursprüngliche Zeichenfolge aus der beschädigten Zeichenfolge

Question

Ich habe eine beschädigte Zeichenfolge mit Leerzeichen an falschen Stellen und ein Wörterbuch mit den richtigen Wörtern gegeben. Die Herausforderung besteht darin, die ursprüngliche Zeichenfolge mithilfe des Wörterbuchs zu erstellen.

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

ich einen rekursiven Ansatz denke da jeden Charakter gibt es 2 Möglichkeiten, kann es ein neues Wort oder ein Teil des vorherigen Wortes sein. Gehe ich in die richtige Richtung? Gibt es einen besseren Ansatz für dieses Problem?

Answer 1

Sie sollten alle Leerzeichen entfernen, dann Wörter im Wörterbuch mit dem Kopf der Zeichenfolge übereinstimmen und rekursiv überprüfen, ob das Ende der Zeichenfolge in der übereinstimmen kann gleiches Verhalten. Sie möchten, dass die rekursive Funktion alle Übereinstimmungen zurückgibt, z. B. ein Array oder Baum von Strings, die übereinstimmen. Ich habe es gerade geschrieben, um die Ausgabe unten auszudrucken, aber Sie könnten stattdessen die Ausgabe speichern.

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 

Dann rufen Sie die Funktion von printAllMatches("", stringWithoutSpaces). Wenn die Vorderseite von stringWithoutSpaces verarbeitet wird, wird sie auf head verschoben.

Answer 2

Angenommen, wir möchten nur eine mögliche Antwort finden.

Rekursion ist eine gute Methode zu verwenden. WIE das:

OK, wir können jetzt eine Antwort finden, ABER was ist das Große (O)?

Darüber hinaus haben wir zwei Positionen zu beschleunigen:

A., wenn wir sehen, wenn ein Wort in einem Wörterbuch, können wir Trie-Baum (http://en.wikipedia.org/wiki/Trie) verwenden zu beschleunigen. So vermeiden wir suchen es von Rot-Schwarz-Baum jedes Mal

B. sollten wir die berechnete Antwort erinnern: dynamische Programmierung ist eine gute Lösung, da Sie rekursive jetzt verwenden, können Sie die dynamische Programmierung memoization verwenden [What is the difference between memoization and dynamic programming?

Jetzt ist die Komplexität O (n * k)

Answer 3

Nach dem Entfernen von Leerzeichen aus der Zeichenfolge können wir dynamische Programmierung verwenden, um zu überprüfen, ob wir die Zeichenfolge in Wörter im Wörterbuch enthalten können.

Im Folgenden finden Sie C++ Code für die gleichen -

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]; 
    } 

}