題目
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
分析
第一眼看到這個(gè)題目，或許最直覺(jué)的方法就是，把s分成若干份克蚂，這樣有很多種分法孟岛，對(duì)每一種分法丧没，檢查每一份word是否在word list里婚瓜。
但是這樣顯然特別慢,可以有(n choose 1) + (n choose 2) + ... (n choose n)種分法编兄。
下面用dp思路解決這個(gè)問(wèn)題
定義dp[i] = true when s[i...n] has a word break, false otherwise
base case是dp[i] = whether s[i...n] is in word list, for all i
s: |____________|_______|
1........................k.............n
假設(shè)我們已經(jīng)知道了dp[k+1...n], dp[k+2, ...n], ... dp[n]，那么如何知道[k...n]之間是否有word break?
for i = k to n
dp[k] = true if s[k...i] is a word in word list and dp[i+1] is true
如果從index k到i之間的string在word list里面，而且我們已經(jīng)知道從index i+1 到n之間的string有word break酣栈，那么就可以確定s[k...n]之間是否有word break了园骆。
因?yàn)閎asecase是dp[n], 有了dp[n]可以計(jì)算dp[n-1], dp[n-2], 進(jìn)而計(jì)算出dp[1]。也就是可以計(jì)算出s[1...n]之間是否有word break灿椅。
以上的解釋是以string的index是從1開(kāi)始算的，代碼里是以0開(kāi)始，請(qǐng)注意區(qū)分一下
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
HashMap<String, Boolean> wordMap = new HashMap<String, Boolean>();
// Put each word into wordMap for quick lookup
for(String word : wordDict) {
wordMap.put(word, true);
}
// dp array
boolean[] hasWordBreak = new boolean[n+1];
// Does string from index n-1 (to n-1) have a word break?
for(int i = n-1; i >= 0; i--) {
String curr_word = s.substring(i, n);
hasWordBreak[i] = wordMap.get(curr_word) != null;
}
hasWordBreak[n] = false;
for(int k = n-1; k >= 0; k--) {
for(int i = k; i < n; i++) {
String curr_word = s.substring(k, i + 1);
if(wordMap.get(curr_word) != null && hasWordBreak[i + 1]) {
hasWordBreak[k] = true;
break;
}
}
}
return hasWordBreak[0];
}
時(shí)間復(fù)雜度為O(n^2), 因?yàn)橹饕挠?jì)算發(fā)生在一個(gè)二維循環(huán)里
這道題如果用常規(guī)的方法來(lái)做肯定會(huì)超時(shí)
回頭看看這篇文章如何解這道題
http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/
