【LeetCode】【算法】139. 单词拆分

LeetCode 139. 单词拆分

题目

给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例：
输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true
解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。

思路

思路：动态规划，数组boolean dp[0~i]表示字符串[0,i-1]位是否可以被wordDict中的内容表示

1. 动态规划数组初始化：第0位字符串为空，所以肯定可以被表示，dp[0]=true;
2. 嵌套循环填充动态规划数组：
   I. 第一个for循环遍历字符串for(int i=0; i<s.length(); i++)
   II. 第二个for循环遍历从第i位起的字符串for(int j=i+1; j<s.length()+1; j++)，在第二个for循环中，如果满足dp[i] && wordDict.contains(s.subString(i,j))，则将dp[j]置为true。这个条件如果满足的话，意思是0~i-1位可以被表示，且i~j也能被表示，则将dp[j]（0~j）置为true以表示wordDict可以表示字符串的0~j位
3. 返回dp[s.length()]

代码

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // dp[i]表示从[0~i]可以被wordDict中的内容表示
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true; // 表示空字符串可以被wordDict表示
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j < s.length() + 1; j++) {
                // 0~i可被wordDict中的元素表示 && 后面也能被wordDict表示的话
                if (dp[i] && wordDict.contains(s.substring(i, j))){
                    dp[j] = true;
                }
            }
        }
        return dp[s.length()];
    }
}