来源：LeetCode
难度：中等
描述：
给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
- 拆分时可以重复使用字典中的单词。
- 你可以假设字典中没有重复的单词。
示例1：
示例2：
输入: s = “applepenapple”,wordDict=[“apple “,” pen”]
输出：true
解释：返回 true因为”applepenapple”可以被拆分成”apple pen app1″。
注意你可以重复使用字典中的单词。
示例3：
输入:s = “catsandog”，wordDict=[“cats”,”dog”,”sand”,”and”,”cat”]
输出:false
分析：题意还是很明确的，给咱们一个字符串和一个包含单词的数组，让咱们判断字符串全部拆分成数组中的单词，该题要求用空格拆分，那咱们按顺序拆分判断就行，以下是具体解法
解题
方法一：暴力递归法
思路：如分析，咱们按顺序拆分字符串，如果该单词在数组中，那么将剩余的字符串继续拆分，直到字符串为空，即说明能够完全拆分
代码：
1public boolean wordBreak(String s, List<String> wordDict) {
2 //当串s为空时，表明全部能够拆分成数组中的元素
3 if (s == null || s.length() == 0) {
4 return true;
5 }
6 //这里利用set，因为hashSet contains方法为O(1)复杂度，List为O(n) 复杂度
7 Set<String> strings = new HashSet<>(wordDict);
8 for (int i = 1; i <= s.length(); i++) {
9 if (strings.contains(s.substring(0, i))) {
10 //递归剩余的串
11 if (wordBreak(s.substring(i), wordDict)) {
12 return true;
13 }
14 }
15 }
16 return false;
17}题外话：暴力永远滴神
方法二：动态规划
思路：这里我们申请一个辅助数组dp，长度为n + 1， 每一位用来表示该位置前面的元素能否按照数组中的单词完全拆分，即dp[i] 表示字符串的第 0 ~ i 位能否用数组中的单词完全拆分
- 首先 dp[0] = true，因为辅助数组长为n+1，第0位代表空字符串，一定能被切分
- 紧接着咱们遍历字符串每一位，假设dp[i] = true，并且 [i ~ j]能组成数组中的单词，那么一定有 dp[j] = true，即 0 ~ i 能被拆分，当i ~ j能被拆分时，那么一定有0 ~ j 可以被拆分
举个例子：
| l | e | e | t | c | o | d | e | |
| true | false | false | false | true | false | false | false | true |
题外话：不多比比，咱直接上代码吧
代码：
1public boolean wordBreak(String s, List<String> wordDict) {
2 if (s == null || s.length() == 0) {
3 return true;
4 }
5 //这里利用set，因为hashSet contains方法为O(1)复杂度，List为O(n) 复杂度
6 Set<String> strings = new HashSet<>(wordDict);
7 boolean[] dp = new boolean[s.length() + 1];
8 dp[0] = true;
9 //遍历每个位置
10 for (int i = 1; i <= s.length(); i++) {
11 //判断该位置能否被完全拆分
12 for (int j = 0; j <= i; j++) {
13 //0 ~ j 能完全拆分 & j ~ i 完全拆分 那么一定有 0 ~ i 完全拆分
14 if (dp[j] && strings.contains(s.substring(j, i))) {
15 dp[i] = true;
16 break;
17 }
18 }
19 }
20 return dp[s.length()];
21}
时间复杂度：O(n2)
空间复杂度：O(n)
以上仅是个人思路解法
输入: s = “applepenapple”,wordDict=[“apple “,” pen”]输出：true解释：返回 true因为”applepenapple”可以被拆分成”apple pen app1″。注意你可以重复使用字典中的单词。
转载请注明：XAMPP中文组官网 » 动态规划7–单词拆分