1

我正在閱讀有關動態規劃的一個問題。問題如下:將一串字符分解爲有效字

將長度爲n的字符串拆分爲有效的 單詞序列。假設有一個數據結構告訴你一個字符串 在常量時間內是否是一個有效的單詞。

我解決了它我的一些方式,但後來我讀了解決方案是以下幾點:

創建一個表T [N]它說,T [i]爲真,如果子 [0 ... i]可以分解爲一系列有效的單詞。當且僅當 存在AJ,0 < = j的< = K-1,其中T [j]爲TRUE,並且S(J,K)是一個有效的 字

這是經典的T [i]爲真爲DP制定但不是錯的?不是應該:

T [i]爲真當且僅當存在AJ,0 < = j的< = K-1,其中T [j]爲TRUE,並且 S(J + 1,K )是一個有效的單詞或S(0,i)是一個有效的單詞

否則,我怎麼看不到的表可以從此例如用於字符串來構建:itsthe我們將永遠不會有T[2] = true,如果我們不考慮到its是一個字和下一個序列the ie S(2+1, N) for j = 2.
我在這裏嗎?但是,我們如何才能找到真正的單詞?
示例代碼我爲我的理解作出(s.substring(i,j)i including j-1返回字符串中的Java):

int i = 0 
for(; i < s.length(); i++){ 
    for(int j = 0; j > i; j++){ 
     if(T[j] && dictionary.contains(s.substring(j + 1, i)){ 
      T[i] = true; 
      break; 
     } 
    } 
    if(dictionary.contains(s.substring(0, i + 1)){ 
     T[i] = true; 
    } 
} 

回答

1

你是對所有的更正。

如果你想重建實際的單詞添加一個表格數組,它會告訴你最後一個字長你用來設置t[i]true。讓我們稱此陣列L[i]

T [i]爲真當且僅當存在AJ,0 < = j的< = K-1,其中T [j]爲TRUE,並且 S(j + 1,k)是一個有效的單詞OR S(0,i)是否是一個有效的單詞? 在第一個 的情況下,你在後面設置L[i] = j - L[i] = i

然後添加你只需要從L[n],其中n是給定的字符串的總長度遞歸回結束。

+0

在'L'是存儲在索引或長度是多少? – Cratylus

+0

@Cratylus索引。然而,因爲你只是在分割整個字符串感興趣,那麼這兩個在某種程度上是重合的。但是,即使您有興趣分割可能的最長部分,也可以使用我建議的方法。 –

+0

所以'L [n]'會給出最後一個單詞的索引,然後我去'L [n-1]'上一個單詞,然後'L [n-2]'等等? – Cratylus

0

這取決於你的符號是什麼意思,特別是選擇子序列。混合方括號和圓括號,「substring [0 ... i]」和「S(j + 1,k)」;我建議我們總是包括左手指數,而不是右手指數。有時通過在左側使用方括號並在右側使用圓括號來明確這一點:S [0 ... i)。

如果我們這樣做,那麼原來的措辭是幾乎正確;我和k之間存在一些混淆,我認爲這應該是相同的,並且i = 0的情況處理不正確。 (與此相關的,我認爲當n = 0(空字符串)也不會正確的修改處理。)

Create a table T[N] which says that T[i] is true if the substring S[0...i) 
can be broken into a sequence of valid words. T[i] is true iff i = 0 OR 
(there exists a j, 0<=j<i, where T[j] is true AND S[j...i) is a valid word). 
+0

符號不是我的。我只能假設'[0..i]'是爲了包含'i',因爲你指出 – Cratylus