LeetCode 139. 单词拆分

139. 单词拆分

解题思路

• BFS
• 递归搜索 + 保存递归返回值 = 记忆化搜索
• 去掉递归中的「递」，只保留「归」的部分，即自底向上计算

状态定义

• 用一个布尔数组 $f[i]$ 来表示字符串 $s$ 的前 $i$ 个字符是否可以被拆分为字典中的单词。
  初始化
• $f[0] = true$，表示空字符串是可以拆分的。
  状态转移
• 对于每个 $i$，从 $j = i - 1$ 遍历到 $i - maxLen$（这里 $maxLen$ 是字典中单词的最大长度）。如果 $s[j, i)$ 在字典中，并且 $f[j]$ 为 $true$，说明从 $0$ 到 $j$ 的部分可以拆分，而 $s[j, i)$ 是一个合法的单词，因此 $f[i]$ 也应该为 $true$。
  优化
• 从字典中找出单词的最大长度 $maxLen$，剪枝

参考代码

BFS

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> curLevel = new HashSet<>();
        curLevel.add("");

        while(!curLevel.isEmpty()) {
            Set<String> nextLevel = new HashSet<>();
            for(String str : curLevel) {
                if(str.equals(s)) {
                    return true;
                }
                for(String word : wordDict) {
                    String tmp = str + word;
                    // 判断tmp长度是否不超过s，且是s的前缀
                    if(tmp.length() <= s.length() && tmp.equals(s.substring(0, tmp.length()))) {
                        nextLevel.add(tmp);
                    }
                }
            }
            curLevel = nextLevel;
        }
        return false;
    }
}

记忆化搜索

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 剪枝
        int maxLen = 0;
        for(String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }
        Set<String> words = new HashSet<>(wordDict);

        int n = s.length();
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        // 从右到左
        return dfs(n, maxLen, s, words, memo) == 1;
    }

    private int dfs(int i, int maxLen, String s, Set<String> words, int[] memo) {
        // 成功拆分
        if(i == 0) {
            return 1;
        }
        if(memo[i] != -1) {
            return memo[i];
        }

        for(int j = i - 1; j >= Math.max(i - maxLen, 0); j --) {
            // s[j, i)存在于words中 且 递归检查前缀s[0:j)是否可以拆分
            if(words.contains(s.substring(j, i)) && dfs(j, maxLen, s, words, memo) == 1) {
                return memo[i] = 1; // s[0:i)可以被拆分为字典中的单词
            }
        }
        return memo[i] = 0;
    }
}

转换为递推

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 剪枝
        int maxLen = 0;
        for(String word : wordDict) {
            maxLen = Math.max(maxLen, word.length());
        }
        Set<String> words = new HashSet<>(wordDict);

        int n = s.length();
        // 字符串s的前i个字符（即s[0:i)）是否可以被拆分为字典中的单词
        boolean[] f = new boolean[n + 1];
        f[0] = true;
        for(int i = 1; i <= n; i ++) {
            // 只需要判断maxLen长度范围内的字符串是否在words
            for(int j = i - 1; j >= Math.max(i - maxLen, 0); j --) {
                if(words.contains(s.substring(j,i)) && f[j]) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n];
    }
}