单词拆分 | echo

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict*，判定 *s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

示例 1：

1
2
3

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1 2	输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

我们定义 dp[i] 表示字符串 s 前 i 个字符组成s的字符串 s[0…i - 1] 是否能被空格拆分成若干个字典中出现的单词。对于字符串 s[0 … i - 1]，我们需要枚举每一个分割点，位置为 j ，将其分为两个字符串，得到 s[0 … j - 1]，s[j … i - 1]，如果两个字符串均合法，那么将其拼接起来的字符串同样合法。由于计算 dp[i] 时已经计算出了 dp[0 … i - 1] 的值，因此字符串 s[0 … j - 1] 是否合法由 dp[j] 可知，剩下的我们只用看 s[j … i - 1] 是否合法，因此得到如下转移方程：
$$
dp[i]=dp[j] & & checks(s[j…i-1])
$$
其中 checks(s[j…i-1]) 表示子串 s[j … i - 1] 是否出现在字典中。初始化dp[0] = true;

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet(wordDict);
        int n = s.length();
        //dp[i] 表示 s 中 以 下标 i-1 结尾的字符串可否被 wordDict 拆分
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        for(int i=1; i<=n; ++i){
            //利用下标 j 将 下标为 0 ~ i-1 的字符串分割成两个字符串,依次判断所有情况。
            for(int j=0; j<i; ++j){
                if(dp[j] && set.contains(s.substring(j,i)) ){
                    dp[i] = true;
                }
            }
        }
    return dp[n];
    }
}

时间复杂度 O(n^2)，空间复杂度O(n)