Leetcode 139 单词拆分

题意理解：

        给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

        这道题目可以用回溯也可以用动态规划来解决。

        这里采用动态规划来解决这个问题，将其转换为一个背包问题。

        wordDict表示可用的元素，其中元素可以被重复使用。

        字符串s就是target，是要凑出来的目标。

        且这里强调顺序，所以这里求的是排列数。

解题思路：

        已知元素集合是wordDict, 元素可以重复使用，所以是完全背包问题。

        其次强调凑出target的顺序，所以这里求排列数，所以双for循环先背包后物品遍历。

        此时dp[j]表示长度为j的字符串是否能被指定的元素组成。其值为true或false.

        

        假设此时字符串长度为j

        其中dp[i]=true 表示长度为i的部分符合条件

        且s.subString(i,j)在元素集合里

        则说明长度为j的字符串可以由元素集里的元素组成，即dp[j]=true.

1.解题

public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp=new boolean[s.length()+1];
        Arrays.fill(dp,false);
        dp[0]=true;//无实际意义
        for(int j=1;j<=s.length();j++){//遍历包
            for(int i=0;i<j;i++){//遍历元素
                /**
                 * dp[i]=true表示之前的数组是符合条件
                 * s.subString(i,j) 从当前位置取j个长度，该元素是否在指定元素里、
                 * 若之前的数组符合条件，背包可放入的元素在集合里
                 * 则整个长度为j得到字符串能由元素组成，即dp[j]=true
                 */
                if(dp[i]&&wordDict.contains(s.substring(i,j))){//dp[i]=true且
                    dp[j]=true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

2.分析

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

空间复杂度：O(n)