139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
解题思路
这个题还是有一点难度的，需要明确的是，字典中是存在前缀词的，比如“aaa”,"aaaa"可以同时存在于字典中，所以基本排除了On的可能性。
第一种思路是利用递归，方法是按从左到右顺序遍历字符串，将当前第i个字符，与之前的字符拼接成单词，在字典中查找，如果字典中存在该单词，那么继续递归遍历s从i到结尾的子字符串，同时还要考虑第i个字符并不是单词结尾的可能，继续向后遍历。一直到整个字符串s的尾部，如果刚好有个单词的结尾在s的尾部，那么结束遍历。
语言的描述有点抽象，但是代码写起来是很简洁的。
代码实现如下:
public static boolean wordBreakHist(String s, List<String> wordDict) {
char[] arr = s.toCharArray();
String curWord = "";
for (int i = 0; i < arr.length; i++) {
curWord += arr[i];
if (wordDict.contains(curWord)) {
if (i == arr.length - 1) {
return true;
}
if (wordBreak(s.substring(i + 1), wordDict)) {
return true;
}
}
}
return false;
}
但是迭代效率太低，跑到这个用例的时候报超时了。
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
继续优化一下思路，考虑用动态规划来做。
首先我们知道，当s可以被拆分的时候，s必然是由一个单词结尾的。也就说s是否可拆分，可以简化为，能否找到一个位置i，使得s(0,i)为一个可拆分的字符串，而s(i+1,leng)为一个单词。
即 dp[length] = max{dp[i] * s(i,leng)}； 其中dp[i]=1表示s(0,i)为一个可拆分的字符串，s(i,leng)=1表示s(i+1,leng)为一个单词。
根据这个思路，我们对s进行遍历，显然由于每次dp[i]的变化都会影响后续dp的计算，所以我们需要On2的遍历次数。或者说，我们需要对s字符串中，每一个可以组成字符串的子串进行计算，所以需要On2的遍历，代码中s(j,i)即代表每种可能的结尾单词。
另外，我们需要计算一下dp的初值，显然当s为一个单词时，dp[s]=1
即 dp[s] = dp[0] * s(0,leng);
由此我们可以求得dp[0]=1。
以下是代码实现：
public static boolean wordBreak(String s, List<String> wordDict) {
char[] arr = s.toCharArray();
boolean[] dp = new boolean[arr.length + 1];
dp[0] = true;
for (int i = 0; i <= arr.length; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[arr.length];
}
两种方法比较，使用动态规划确实要比迭代快很多。
另附测试代码：
public static void main(String[] args) {
List<String> wordDict = new ArrayList<>();
wordDict.add("aaaa");
wordDict.add("aaa");
System.out.println(wordBreak("aaaaaaa", wordDict));
List<String> wordDict2 = new ArrayList<>();
String test = "";
for (int i = 0; i < 10; i++) {
test += "a";
String test2 = test;
wordDict2.add(test2);
}
long start = System.currentTimeMillis();
System.out.println(wordBreak(
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
wordDict2));
long end = System.currentTimeMillis();
System.out.println("wordBreak cost "+(end-start));
start=end;
System.out.println(wordBreakHist(
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab",
wordDict2));
end = System.currentTimeMillis();
System.out.println("wordBreakHist cost "+(end-start));
}
