題目：

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given

s = "leetcode",

dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

題解：

這道題的題解轉(zhuǎn)載自Code ganker，他寫的很好。地址：http://blog.csdn.net/linhuanmars/article/details/22358863

“原題鏈接:http://oj.leetcode.com/problems/word-break/

這道題仍然是動態(tài)規(guī)劃的題目，我們總結(jié)一下動態(tài)規(guī)劃題目的基本思路。首先我們要決定要存儲什么歷史信息以及用什么數(shù)據(jù)結(jié)構(gòu)來存儲信息。然后是最重要的遞推式，就是如從存儲的歷史信息中得到當(dāng)前步的結(jié)果。最后我們需要考慮的就是起始條件的值。

接

下來我們套用上面的思路來解這道題。首先我們要存儲的歷史信息res[i]是表示到字符串s的第i個元素為止能不能用字典中的詞來表示，我們需要一個長度

為n的布爾數(shù)組來存儲信息。然后假設(shè)我們現(xiàn)在擁有res[0,...,i-1]的結(jié)果，我們來獲得res[i]的表達(dá)式。思路是對于每個以i為結(jié)尾的子

串，看看他是不是在字典里面以及他之前的元素對應(yīng)的res[j]是不是true，如果都成立，那么res[i]為true，寫成式子是

假

設(shè)總共有n個字符串，并且字典是用HashSet來維護(hù)，那么總共需要n次迭代，每次迭代需要一個取子串的O(i)操作，然后檢測i個子串，而檢測是

constant操作。所以總的時間復(fù)雜度是O(n^2)(i的累加仍然是n^2量級)，而空間復(fù)雜度則是字符串的數(shù)量，即O(n)。代碼如下：

”

1?public?boolean?wordBreak(String?s,?Set?dict)?{

2?????if(s==null?||?s.length()==0)

3?????????return?true;

4?????boolean[]?res?=?new?boolean[s.length()+1];

5?????res[0]?=?true;

6?????for(int?i=0;i

7?????{

8?????????StringBuilder?str?=?new?StringBuilder(s.substring(0,i+1));

9?????????for(int?j=0;j<=i;j++)

10?????????{

11?????????????if(res[j]?&&?dict.contains(str.toString()))

12?????????????{

13?????????????????res[i+1]?=?true;

14?????????????????break;

15?????????????}

16?????????????str.deleteCharAt(0);

17?????????}

18?????}

19?????return?res[s.length()];

20?}

總結(jié)

以上是生活随笔為你收集整理的leetcode word break java,Word Break leetcode java的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。