使用動態編程將字符串拆分爲一個有效字符串

Question

我需要找到一個動態編程算法來解決這個問題。我嘗試過但無法弄清楚。這裏是問題：

給你一串n個字符s [1 ... n]，你認爲它是一個損壞的文本文件，其中所有的標點符號都已經消失了（所以它看起來像「itwasthebestoftimes ......「）。您希望使用字典來重建文檔，該字典以布爾函數dict（*）的形式提供，以便對於任何字符串w，如果w是有效字，則dict（w）的值爲1，並且值爲0除此以外。

1. 給出一個動態規劃算法，確定字符串s [*]是否可以重組爲一個有效詞序列。運行時間應該至多爲O（n^2），假設每次調用字典都需要單位時間。
2. 如果字符串有效，使您的算法輸出相應的單詞序列。

Answer 1

字符串s []可能會被分成多種方式。下面的方法找到我們可以分割s []的最大單詞數。下面是該算法

bestScore的草圖/僞代碼[I] - >存儲在其第i個字符可以被分開單詞的最大數量（這將是MINUS_INFINITY否則）

for (i = 1 to n){ 
    bestScore[i] = MINUS_INFINITY 
    for (k = 1 to i-1){ 
     bestScore[i] = Max(bestSCore[i], bestScore[i-k]+ f(i,k)) 
    } 
} 

其中f （I，K）被定義爲：

f(i,k) = 1 : if s[i-k+1 to i] is in dictionary 
     = MINUS_INFINITY : otherwise 

bestScore [n]的將存儲字的最大數量，其中S []可以被分割（如果該值MINUS_INFINIY，S []不能拆分）

顯然，運行時間爲O（n^2）

由於這看起來像一本教科書練習，我不會編寫代碼來重構實際的拆分位置。

Answer 2

讓你的壓實文檔的長度爲N.

令B（n）是一個布爾值：如果該文檔可以被分成從位置n處的文檔中開始的話。

b（N）爲真（因爲空字符串可以分成0個字）。給定b（N），b（N-1），... b（N-k），你可以通過考慮以字符N - k - 1開始的所有單詞來構造b（N - k - 1）有b（N - k - 1 + len（w））集，然後將b（N - k - 1）設爲真。如果沒有這樣的單詞，則將b（N - k - 1）設置爲false。

最終，您計算b（0），它告訴您是否可以將整個文檔拆分爲單詞。

在僞代碼：

def try_to_split(doc): 
    N = len(doc) 
    b = [False] * (N + 1) 
    b[N] = True 
    for i in range(N - 1, -1, -1): 
    for word starting at position i: 
     if b[i + len(word)]: 
     b[i] = True 
     break 
    return b 

有一些技巧，你可以做的就是「字開始位置i」高效，但你要求的O（N^2）算法，所以你可以查找字典中從i開始的每個字符串。

要生成的話，就可以修改上述算法來存儲好詞語，或只是產生這樣的：

def generate_words(doc, b, idx=0): 
    length = 1 
    while true: 
    assert b(idx) 
    if idx == len(doc): return 
    word = doc[idx: idx + length] 
    if word in dictionary and b(idx + length): 
     output(word) 
     idx += length 
     length = 1 

這裏b是該算法的第一部分產生的布爾數組。

Answer 3

0123pDp很明顯，但如果你知道字典的話，我想你可以使用一些預計算來讓它在O(N)中更快。 Aho-Corasick

Answer 4

C++中的DP解決方案：

int main() 
{ 
    set<string> dict; 
    dict.insert("12"); 
    dict.insert("123"); 
    dict.insert("234"); 
    dict.insert("12345"); 
    dict.insert("456"); 
    dict.insert("1234"); 
    dict.insert("567"); 
    dict.insert("123342"); 
    dict.insert("42"); 
    dict.insert("245436564"); 
    dict.insert("12334"); 

    string str = "123456712334245436564"; 

    int size = str.size(); 
    vector<int> dp(size+1, -1); 
    dp[0] = 0; 
    vector<string > res(size+1); 
    for(int i = 0; i < size; ++i) 
    { 
     if(dp[i] != -1) 
     { 
      for(int j = i+1; j <= size; ++j) 
      { 
       const int len = j-i; 
       string substr = str.substr(i, len); 
       if(dict.find(substr) != dict.end()) 
       { 
        string space = i?" ":""; 
        res[i+len] = res[i] + space + substr; 
        dp[i+len] = dp[i]+1; 
       } 
      } 
     } 
    } 
    cout << *dp.rbegin() << endl; 
    cout << *res.rbegin() << endl; 

    return 0; 
} 

Answer 5

爲了形式化什麼@MinhPham建議。

這是一個動態編程解決方案。

給定一個字符串str，讓

B [I] =真，如果子串STR [0 ... I]（含）可以分成有效單詞。

將一些起始字符添加到str，例如！，以表示空白字。 str =「！」 + STR

基礎案例是空字符串，所以

B [0] =真。

對於迭代情況：

B [j]的=真，如果B [I] == TRUE和STR [i..j]是一個字對於所有的i <Ĵ

Answer 6

以下是針對此問題的O（n^2）解決方案。

void findstringvalid() { 
string s = "itwasthebestoftimes"; 
set<string> dict; 
dict.insert("it"); 
dict.insert("was"); 
dict.insert("the"); 
dict.insert("best"); 
dict.insert("of"); 
dict.insert("times"); 

vector<bool> b(s.size() + 1, false); 
vector<int> spacepos(s.size(), -1); 
//Initialization phase 
b[0] = true; //String of size 0 is always a valid string 
for (int i = 1; i <= s.size(); i++) { 
    for (int j = 0; j <i; j++) { 
     //string of size s[ j... i] 
     if (!b[i]) { 
      if (b[j]) { 
       //check if string "j to i" is in dictionary 
       string temp = s.substr(j, i - j); 
       set<string>::iterator it = dict.find(temp); 
       if (it != dict.end()) { 
        b[i] = true; 
        spacepos[i-1] = j; 
       } 
      } 
     } 
    } 
} 
if(b[s.size()]) 
    for (int i = 1; i < spacepos.size(); i++) { 
     if (spacepos[i] != -1) { 
      string temp = s.substr(spacepos[i], i - spacepos[i] + 1); 
      cout << temp << " "; 
    } 
    } 
}