139.单词拆分

题目描述

题解

动态规划

初始化一个布尔型的dp 数组, dp[i]表示字符串s 从首字符到第i 位的子串在字典中是否存在.

需要一个双循环的结构, 思路就是暴力遍历, 从第i 位出发

• 令j=i + 1, 判断s[i:j]是否在字典中, 如果在字典中则dp[j] =true

最终返回dp[n]

public boolean wordBreak(String s, List<String> wordDict) {
    if (s.length() < 1) {
        return false;
    }

    int len = s.length();

    boolean[] dp = new boolean[len + 1];
    dp[0] = true;

    for (int i = 0; i < len; i++) {
        if (dp[i]){
            for (int j = i + 1; j <= len; j++) {
                String subStr = s.substring(i, j);
                if (wordDict.contains(subStr)) {
                    dp[j] = true;
                }
            }
        }
    }

    return dp[len];
}

记忆化回溯

从字符串的左边开始, 如果符合字典中的某个字符串, 就将其这部分截去, 从剩余的字符串开始继续去匹配字典中的内容.

每匹配上了一段, 就将其截去

public class lc139 {
    HashMap<String, Boolean> memo = new HashMap<>();

    public boolean wordBreak(String s, List<String> wordDict) {
        return process(s, wordDict);
    }

    private boolean process(String s, List<String> wordDict) {
        if (s.isBlank()) {
            return true;
        }

        if (memo.containsKey(s)) {
            return memo.get(s);
        }

        boolean res = false;
        for (String subStr : wordDict) {
            if (s.startsWith(subStr)) {
                if (process(s.substring(subStr.length(), s.length()), wordDict)) {
                    res = true;
                    break;
                }
            }
        }

        memo.put(s, res);
        return res;
    }
}