139.单词拆分

目标

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 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 中的所有字符串 互不相同

思路

已知一个字符串列表 wordDict 和一个字符串 s，问能否用列表中的元素拼成该字符串，列表中的元素可以重复使用。

很明显需要使用动态规划来求解，假设当前列表元素 word 的长度为 l，子字符串 sub 的长度为 i，如果 sub.substring(0, i-l) 能由字典中的词拼成并且 word.equals(sub.substring(i-l, l)) 那么 sub 也能由字典中的词拼成。

代码

/**
 * @date 2024-06-23 19:58
 */
public class WordBreak139 {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 1; i <= n; i++) {
            for (String word : wordDict) {
                int length = word.length();
                if (length <= i && dp[i - length] && word.equals(s.substring(i - length, i))) {
                    dp[i] = true;
                }
            }
        }
        return dp[n];
    }

    public boolean wordBreak_v1(String s, List<String> wordDict) {
        int n = s.length();
        char[] mem = new char[n + 1];
        Arrays.fill(mem, '2');
        return dfs(s, 0, wordDict, mem) == '1';
    }

    public char dfs(String s, int i, List<String> wordDict, char[] mem) {
        int n = s.length();
        if (i == n) {
            return '1';
        }
        if (mem[i] != '2') {
            return mem[i];
        }
        for (String word : wordDict) {
            if (s.startsWith(word, i) && '1' == dfs(s, i + word.length(), wordDict, mem)) {
                return mem[i] = '1';
            }
        }
        return mem[i] = '0';
    }
}

性能

最快的解法是使用记忆化搜索，可以剪枝缩小搜索范围。