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.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because "leetcode" can be segmented as "leet code".
题意：
给定字符串S和字典wordDict, 判断字符串S是否能由字典中的单词组合而成
思路：
用一维boolean数组记录是否能字符串S是否能被分隔
l e e t c o d e
| T | F | F | F | F | F | F | F | F |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
dp[0]初始化为true, 其他为default的false
dp[s.length() + 1]
i = 1 j = 1, dp[1] 为default F, 没必要再去验证wordDict.contains(s.substring(j,i))
j = 0, dp[0] 为 T ， 验证wordDict.contains(s.substring(0,1)) 为F
i = 2 j = 2, dp[2] 为default F
j = 1, dp[1] 为default F
j = 0, dp[0] 为 T ， 验证wordDict.contains(s.substring(0,2)) 为F
i = 3 j = 3, dp[3] 为default F
j = 2, dp[2] 为default F
j = 1, dp[1] 为default F
j = 0, dp[0] 为 T ， 验证wordDict.contains(s.substring(0,3)) 为F
i = 4 j = 4, dp[4]为default F
j = 3, dp[3] 为default F
j = 2, dp[2] 为default F
j = 1, dp[1] 为default F
j = 0, dp[0] 为 T ， 验证wordDict.contains(s.substring(0,4)) 为T ----> 更新dp[4] = true
| T | F | F | F | T | F | F | F | F |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
代码：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// corner case
if (s == null || s.length() < 1 || wordDict == null || wordDict.size() < 1) {
return false;
}
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
//外层循环scan字符串S
for(int i = 1; i <= s.length(); i++ ){
//内层循环找分割点
for(int j = i; j >= 0; j--){
if(dp[j] && wordDict.contains(s.substring(j,i))){
dp[i] = true;
}
}
}
return dp[s.length()];
}
}