给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例 1：
1
2
3
| 输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
|
示例 2：
1
2
3
4
| 输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
|
示例 3：
1
2
| 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
|
思路
1
2
3
| 这道题仍然是动态规划的题目，我们总结一下动态规划题目的基本思路。首先我们要决定要存储什么历史信息以及用什么数据结构来存储信息。然后是最重要的递推式，就是如从存储的历史信息中得到当前步的结果。最后我们需要考虑的就是起始条件的值。
首先我们要存储的历史信息res[i]是表示到字符串s的第i个元素为止能不能用字典中的词来表示，我们需要一个长度为n的布尔数组来存储信息。然后假设我们现在拥有res[0,...,i-1]的结果，我们来获得res[i]的表达式。思路是对于每个以i为结尾的子串，看看他是不是在字典里面以及他之前的元素对应的res[j]是不是true，如果都成立，那么res[i]为true;
|
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
boolean [] arr=new boolean[s.length()];
String temp =s.substring(0,1);
for(int i =0 ;i<wordDict.size();i++){
if(temp.equals(wordDict.get(i))){
arr[0]=true;
break;
}
}
for(int i =1;i<arr.length;i++){
temp=s.substring(0,i+1);
for(int j =0;j<wordDict.size();j++){
String str=wordDict.get(j);
if(temp.endsWith(str)){
if(str.length()==(i+1)){
arr[i]=true;
break;
}else if(str.length()<(i+1)){
int k =i-str.length();
if(arr[k]==true){
arr[i]=true;
break;
}else {
continue;
}
}
}else{
continue;
}
}
}
return arr[s.length()-1];
}
}
|