动态规划:文章来源:https://www.toymoban.com/news/detail-828358.html
1.先声明dp数组的含义为下标i表示的是在s变量中i前面的字符串是否在wordDict变量中存在,初始化dp【0】来进行后面dp数组的递推。同时要判断截取的值是否在wirdDict中是否存在,还要判断dp【j】的下标的j前面的字符串是否也在wirdDict中,如果都符合条件就给dp【i】赋值true。文章来源地址https://www.toymoban.com/news/detail-828358.html
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
//dp数组的下标i表示的时在s变量中i前面的字符串是否在wordDict变量中存在
boolean[] dp=new boolean[s.length()+1];
//初始化dp【0】来进行后面的dp数组递推
dp[0]=true;
for(int i=1;i<=s.length();i++){
for(int j=0;j<i;j++){
//截取s变量中j-i的值来进行判断是否在wordDict中存在
String st=s.substring(j, i);
//判断条件截取的值在wordDict中,同时j之前的值都在wordDict中,就给dp【i】赋值为true
if(wordDict.contains(st)&&dp[j]==true){
dp[i]=true;
}
}
}
//放回在s中最后一个下标的dp数组值
return dp[s.length()];
}
}
到了这里,关于力扣:139. 单词拆分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!