单词拆分

139.单词拆分

题意

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

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

思路一：动态规划

1. 定义 DP 数组，dp[i] 表示 s 的前 $i$ 位是否可以用 wordDict 中的单词表示。
2. 初始化 dp[0] = true，空字符也可以被表示
3. 遍历字符串 s 的每个字符，对于 wordDict 中的每个单词：
   • 若 dp[i] = true，则表示 s 的前 $i$ 位可以用单词表示；
   • 对于后 [i, n] 位，判断 s[i,...,n] 是否出现在 wordDict 中，如果满足条件，则可以表示，更新对应位置的 dp = true。
4. 最后返回 dp[n] 即可。

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

        return dp[n];
    }
}

思路二：记忆化搜索

1. 使用记忆化函数，保存出现过的 dfs(s)，避免重复计算。
2. 定义递归函数 dfs(s)：
   • 若 s 长度为 $0$，则返回 true，表示已经使用 wordDict 中的单词完成分割；
   • 初始化当前字符串是否可以被分割 res = false；
   • 遍历剩下区间 [i, n]，若剩下字符串也能够完成分割，则返回 true
3. 最后返回 res。

class Solution {

    private boolean dfs(String s, List<String> wordDict, Map<String, Boolean> memo){
        if (s.isEmpty()) return true;

        // 这个状态已经被计算过，则直接返回结果
        if (memo.containsKey(s)) return memo.get(s);

        int n = s.length();
        boolean res = false;
        // 如果剩下的子串s[i,...,n]在字典中且可以分割，则返回true
        for (int i = 1; i <= n; i++){
            String pre = s.substring(0, i);
            if (wordDict.contains(pre)){
                res = dfs(s.substring(i), wordDict, memo) || res;
            }
        }

        // 记录当前结果
        memo.put(s, res);

        return res;
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        Map<String, Boolean> memo = new HashMap<>();  // 记录状态
        return dfs(s, wordDict, memo);
    }
}