139. 单词拆分 - Java 动态规划

原题地址：https://leetcode.cn/problems/word-break/

题解

参考官方题解

设dp[i]为s的前i个字符组成的子串(s.substring(0,i+1))是否能被拆分为单词

我们可以从[0,i]遍历一个j，将[0,i]拆分为[0,j-1]和[j-i]两部分，于是dp[i]就取决于两个因素：

dp[j-1]是否为true
[j-i]这部分字串是否能匹配到wordDict中

若二者皆满足，则我们可以认为子串[0,i]是由一个已知可以被拆分的字串[0,j-1]加上wordDict中的一个单词组成的

那么自然地，我们有dp[i]=true，即：

要注意的是，由于Java中的substring是左闭右开的，即[x,y)，因此对于检查子串[j,i]，我们应当记作substring(j,i+1)

优化：

由于遍历j的时候只要有一种情况满足，我们就可以直接跳出循环并设置dp[i]=true，考虑到wordDict中的单词长度往往远小于s.length，让j从i开始倒序遍历可以节省更多的时间

时间复杂度：O(N^2)

空间复杂度：O(N)

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp=new boolean[s.length()];

        for(int i=0;i<s.length();i++){
            for(int j=i;j>=0;j--){
                if((j==0||dp[j-1])&&check(s,wordDict,j,i+1)){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[dp.length-1];
    }

    boolean check(String s,List<String> wordDict,int begin,int end){
        String substr=s.substring(begin,end);
        for(String checkStr:wordDict){
            if(substr.equals(checkStr))return true;
        }
        return false;
    }
}