🌗 139. 单词拆分

难度: 🌗

• 问题描述
• 解法
• 输出

问题描述

---

解法

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 思路：
        // dp[i] = dp[i - [j]]
        int len = wordDict.size();
        int amount = s.length();
        boolean[] dp = new boolean[amount + 1];
        dp[0] = true;
        for(int i = 1; i <= amount; i ++) {
            for(int j = 0; j < len; j ++) {
                // 假设需要 [j] 处的单词，则 以 i 为最末下标，往前推这个单词必须匹配
                // 且除去这个单词的前面部分也必须匹配
                String cur = wordDict.get(j);
                int size = cur.length();
                if(i - size >= 0 && dp[i - size]) {
                    if(mySol(s, i - size, cur)) {
                        dp[i] = true;
                    }
                }
            }
        }
        return dp[amount] == true;
    }

    private boolean mySol(String s, int from, String cur) {
        int index = from;
        int len = cur.length();
        for(int i = 0; i < len; i ++) {
            if(s.charAt(index + i) != cur.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

---

输出