题目
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".
分析
第一眼看到这个题目，或许最直觉的方法就是，把s分成若干份，这样有很多种分法，对每一种分法，检查每一份word是否在word list里。
但是这样显然特别慢,可以有(n choose 1) + (n choose 2) + ... (n choose n)种分法。
下面用dp思路解决这个问题
定义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
假设我们已经知道了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里面，而且我们已经知道从index i+1 到n之间的string有word break，那么就可以确定s[k...n]之间是否有word break了。
因为basecase是dp[n], 有了dp[n]可以计算dp[n-1], dp[n-2], 进而计算出dp[1]。也就是可以计算出s[1...n]之间是否有word break。
以上的解释是以string的index是从1开始算的，代码里是以0开始，请注意区分一下
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];
}
时间复杂度为O(n^2), 因为主要的计算发生在一个二维循环里
这道题如果用常规的方法来做肯定会超时
回头看看这篇文章如何解这道题
http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/
