Skonstruuj oryginalny ciąg z uszkodzonego ciągu znaków

Question

Dostałem uszkodzony ciąg znaków zawierający spacje znajdujące się w niewłaściwych miejscach i słownik zawierający właściwe słowa. Wyzwaniem jest skonstruowanie oryginalnego ciągu znaków za pomocą słownika.

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

Myślę rekurencyjnej podejście, ponieważ każdy znak Są 2 możliwości, może to być nowe słowo lub część poprzedniego wyrazu. Czy zmierzam w dobrym kierunku? Czy istnieje lepsze podejście do tego problemu?

Answer 1

Powinieneś usunąć wszystkie spacje, a następnie dopasować słowa w słowniku do nagłówka napisu i rekurencyjnie sprawdzić, czy ogon napisu może być dopasowany w taki sam sposób. Chcesz, aby funkcja rekursywna zwracała wszystkie dopasowania, np. tablicę lub drzewo z pasujących łańcuchów. Właśnie napisałem to, aby wydrukować dane wyjściowe poniżej, ale zamiast tego możesz przechowywać dane wyjściowe.

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 

Następnie wywołuje się funkcję przez printAllMatches("", stringWithoutSpaces). Po przetworzeniu przodu stringWithoutSpaces zostaje przeniesiony na head.

Answer 2

Załóżmy, że chcemy tylko znaleźć jedną możliwą odpowiedź.

Rekursja to dobra metoda użycia. PODOBNE:

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, możemy teraz znaleźć odpowiedź, ALE co to jest Big (O)?

Ponadto mamy dwa stanowiska do przyspieszenia:

A. kiedy patrzymy w górę, jeśli słowo jest w słowniku, możemy użyć Trie-drzewa (http://en.wikipedia.org/wiki/Trie), aby przyspieszyć. Więc nie patrzeć na nią z drzewo czerwono-czarne każdym razem

B. powinniśmy pamiętać obliczoną odpowiedź: programowanie dynamiczne jest dobrym rozwiązaniem, ponieważ używasz rekurencyjnych teraz, można użyć programowania dynamicznego memoization [What is the difference between memoization and dynamic programming?

Teraz złożoność to O (n * k)

Answer 3

Po usunięciu spacji ze sznurka możemy użyć programowania dynamicznego, aby sprawdzić, czy możemy rozbić łańcuch na słowa obecne w słowniku.

Poniżej jest kod C++ dla tego samego -

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

}