思路

1.定义dp数组

dp[i]表示，当字符串长度为i时，dp[i]是否可以拼接出来。

2.递推公式

  if(dp[i] && wordDict.contains(s.substring(i,j))){                   dp[j]=true;                 }

如果前i个长度的字符串可以被wordDict拼接并且i-j长度的字符串在wordDict中，则长度为j的字符串也可以拼接出来。

3.初始化

dp[0]=true;不然无法遍历。

4.遍历顺序

完全背包问题，内层循环顺序遍历即可。

外层遍历的是物品，此题的物品比较特殊，需要从字符串中截取，就变为物品的起始下标。

5.打印dp数组

数组的最后一个元素的值就是最后的结果。

代码

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

全民K歌电脑版