代码随想录笔记_动态规划_139单词拆分

代码随想录二刷笔记记录

LC139.单词拆分

---

题目

完全背包

给定一个非空字符串 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

---

思路分析

思路：
wordDict中的单词就是物品,可以重复使用,代表是一个完全背包问题

组成的字符串 subString 的长度就是容量

动态规划五部曲

1.确定dp数组及其下标的含义

dp[j] : 字符串长度为j, dp[j] = true 表示可以subString在 wordDict 中存在
1

2.确定递推公式

根据结果反推：结果: “dp[i] 是 true” ,则代表 [j,i) 的子串在 wordDict 中出现过。
即 str[j,i] = leet -> dp[i] = true，即[0，i] 中存在 [j,i] 的子串属于wordDict，此时 dp[j] 也需要为 true,即代表出现过.

以 leetcode 为例，假设 i = 3 时，则有 subString(0,3) = leet,而 wordDict.contains(leet) && dp[j] = True,则 dp[3] = True
因此，递推公式为

if(wordDict.contains(s.subString) && dp[j] = True){
	dp[i] = true;
}
1
2
3

3.初始化

根据递推公式可知，如果第一次 leet 匹配时，代表subString[0,3] 为 “leet”，此时我们需要 dp[0] 为 true ，才能推导 dp[3] = true.

可知,dp[0] 需要初始化为 true，否则之后的推导都不成立。

并且题目中 “给定一个非空字符串 s”,代表 dp[0] 不会在测试用例中出现，因此可以将 dp[0] 赋值为 true

4.遍历顺序

本题要求的时返回是否出现过 True Or False，与组合和排列无关。

因此，无论哪种顺序都可以

但是本题因为是求子串，即 leetcode -> (l,le,lee,leet,…,et,…,de) 因此，如果把物品放在外层for，则需要用一个容器装 子串的集合，因此选择把物品放在内层for，背包放在外层for

for(int i = 1;i <= s.length();i++){  //背包
	for(int j = 0;j < i;j++){   //物品
	//i=2时 (0,1) (0,2) 子串 -> [l,le] 依次类推 
		if(wordDict.contains(s.subString(j,i)) && dp[j] == true){
			dp[i] = true;
		}
	}
}

1
2
3
4
5
6
7
8
9

5.推演分析
以 s = “leetcode”, wordDict = [“leet”, “code”] 为例

---

代码实现

完整代码实现

public boolean wordBreak(String s, List<String> wordDict) {
		//初始化
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        //遍历
        for(int i = 1;i <= s.length();i++){ //背包
            for(int j = 0;j < i; j++){ //物品
                if(wordDict.contains(s.substring(j,i)) && dp[j]){
                dp[i] = true;
                }
            }
        }
        return dp[s.length()];	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

思路分析2

本题其实也可以用回溯法来做，根据回溯法的递归，可以得到目标Target，则返回 true，反之则返回 false

	private Set<String> set;
    public boolean wordBreak(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        boolean res = backTrack(s, 0);
        return res;
    }
    private boolean backTrack(String s,int startIndex){
        //递归终止条件,下标遍历完目标字符串
        if (startIndex == s.length()){
            return true;
        }
        //单层递归逻辑
        for (int i = startIndex; i < s.length(); i++) {
            String subStr = s.substring(startIndex,i+1);
            if (!set.contains(subStr)){
                continue;
            }
            boolean res = backTrack(s, i + 1);
            if (res) return true;
        }
        return false;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

回溯法如上，但是需要注意测试用例35，会导致回溯超时

测试用例35
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
1
2
3

因此，我们需要加入记忆化数组进行回溯。

	private Set<String> set;
    private int[] memory;
    public boolean wordBreak2(String s, List<String> wordDict) {
        set = new HashSet<>(wordDict);
        //记忆化数组
        memory = new int[s.length()];
        boolean res = backTrack(s, 0);
        return res;
    }
    private boolean backTrack(String s,int startIndex){
        //1.递归终止条件,下标遍历完目标字符串
        if (startIndex == s.length()){
            return true;
        }
        //2.记忆化
        if (memory[startIndex] == -1){
            return false;
        }
        for (int i = startIndex; i < s.length(); i++) {
            String subStr = s.substring(startIndex,i+1);
            if (!set.contains(subStr)){
                continue;
            }
            boolean res = backTrack(s, i + 1);
            if (res) return true;
        }
        //记忆化,遍历完 startIndex - s.length(), 也没有与 subStr 相匹配的字典,代表[startIndex,s.length()]的subStr不存在于wordDict中
        //我们就标记为 -1
        memory[startIndex] = -1;
        return false;
    }

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

---