我正在閱讀有關動態規劃的一個問題。問題如下:將一串字符分解爲有效字
將長度爲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;
}
}
在'L'是存儲在索引或長度是多少? – Cratylus
@Cratylus索引。然而,因爲你只是在分割整個字符串感興趣,那麼這兩個在某種程度上是重合的。但是,即使您有興趣分割可能的最長部分,也可以使用我建議的方法。 –
所以'L [n]'會給出最後一個單詞的索引,然後我去'L [n-1]'上一個單詞,然後'L [n-2]'等等? – Cratylus