【Check 72】2024-05-13 - 139. 单词拆分

[larscheng]

139. 单词拆分

[larscheng]

思路

• dp[i]表示字符串s[0:i-1]能否用字典中的单词拼接出
• i=0时，s为空串 dp[i]=true，其他dp[i]默认值均为false
• dp[i] = dp[j] && check(s[j:i-1])

代码

class Solution {

    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length()+1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i ; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

复杂度

• 时间复杂度：O(n*n)
• 空间复杂度：O(n)