139_单词拆分.md

题目

139. 单词拆分

labuladong 题解思路

相关企业

给你一个字符串 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

提示：

• 1 <= s.length <= 300
• 1 <= wordDict.length <= 1000
• 1 <= wordDict[i].length <= 20
• s 和 wordDict[i] 仅由小写英文字母组成
• wordDict 中的所有字符串 互不相同

代码

回溯

时间复杂度 O(N^2^)

class Solution {

    Set<String> set = new HashSet<>();

    // 用来统计当前的mem[i] 前面的字符是否在词典中
    // 0 1 -1
    int[]mem;

    public boolean wordBreak(String s, List<String> wordDict) {
        int n=s.length();
        mem = new int[n];
        for(var str : wordDict){
            set.add(str);
        }
        return traverse(s.toCharArray(),0);
    }

    private boolean traverse(char[]cs,int idx){
        if(idx==cs.length){
            return true;
        }
        if(mem[idx]!=0){
            return mem[idx]==1;
        }

        for(int i=idx;i<cs.length;i++){
            // char[] start len 
            if(set.contains(new String(cs,idx,i-idx+1))){
                if(traverse(cs,i+1)){
                    return true;
                }
            }
        }
        mem[idx]=-1;
        // 如果在遍历过程中都没有匹配完毕, 那么返回 false
        return false;        
    }
}

DP

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 通过set判断是否在词典中
        Set<String> set = new HashSet();
        for(String str : wordDict){
            set.add(str);
        }
        boolean []dp=new boolean[s.length()+1];
        dp[0]=true;
        for(int i=1;i<dp.length;i++){
            for(int j=0;j<i;j++){
                String str= s.substring(j,i);
                dp[i]|=set.contains(str) && dp[j];
            }
        }
        return dp[s.length()];
    }
}

另一种DP的做法是不使用Set , 通过equals判断

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        var n = s.length();
        boolean[]dp = new boolean[n+1];
        dp[0]=true;
        for(int i=0;i<=n;i++){
            if(!dp[i]) continue;
            for(String word : wordDict){
                if(word.length()+i<=n && s.substring(i,i+word.length()).equals(word)){
                    dp[i+word.length()]=true;
                }
            }
        }
        return dp[n];
    }
}

DP-GO

func wordBreak(s string, wordDict []string) bool {
    // DP做法
    n := len(s)
    // dp[i]表示前i个字符是否在词典中
    dp := make([]bool, n+1)
    dp[0] = true
    for i := 0; i <= n; i++ {
        if !dp[i] {
            continue
        }
        // 遍历 i 条件下的字典
        for _, str := range wordDict {
            l := len(str)
            if  l+i <= n && s[i : i+l] == str {
                dp[i+l] = true
            }
        }
    }
    return dp[n]
}

思路

回溯

每次回溯的时候截取字符串进行判断 , 需要注意一些细节问题

1. mem优化, 否则会超时
2. 注意aaaaaaa => aaa , aaaa 这里的判断的问题

DP(完全背包)

完全背包: 能不能把背包装满(字典中的字符串能否消耗完s)

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。

所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。