美团网站开发费用,wordpress模板制作教程视频,广告公司管理系统软件,外贸网站建设的重要性描述#xff1a;给定一个非空字符串和一个包含非空单次的列表wordDict#xff0c;判定s是否可以被空格拆分成一个或多个在字典中出现的单词。
说明#xff1a; 1 拆分式可以重复使用字典中的单词。 2 你可以假设字典中没有重复的单词。
示例1#xff1a;…描述给定一个非空字符串和一个包含非空单次的列表wordDict判定s是否可以被空格拆分成一个或多个在字典中出现的单词。
说明 1 拆分式可以重复使用字典中的单词。 2 你可以假设字典中没有重复的单词。
示例1 输入 sleetcode wordDict[leet,code] 输出true 解释因为leetcode可以被拆分成leetcode
分析这题让把字符串拆分成一些子串并且判断这些子串是否在字典wordDict中可以使用动态规划的方式进行解决定义动态数组dp[i]:表示字符串前i个字符经过拆分是否存在于字典wordDict中如果要求取dp[i]我们向前截取k个字符串判断子串[i-k1,i]是否存在于wordDict中并且前面的[0,i-k]子串也是否存在于wordDict中;
//函数返回值是布尔类型表征是否能被字典所拆分参数是需要进行判断的String以及字典列表listString
public Boolean stringPartition(String s,ListStringwordDict)
{
//定义Boolean类型的动态数组
Boolean dp[]new Boolean[s.length()];
//首先进行动态数组进行初始化即判断字典中是否存在第一个字母由于substring取得是右开集,所以其取得是[0,1)也就是第一个字母
if(wordDict.contains(s.substring(0,1)))
{
dp[0]true;
}else
{
dp[0]false;
}
//进行动态数组的更新
for(int i1;is.length();i)
{
//如果[0,i1)也就是从0取到i1这个子串存在于字典中就不需要进行下一步动态判断dp[i]直接等于true并直接跳出进行下一个i的判断
if(wordDict.contains(s.substring(0,i1)))
{
dp[i]true;
continue;
}
//如果前面不成立就进行往前判断判断子串[j][i]子串是否存在以及dp[j-1]是否存在两者均成立时表明可以进行分割
for(int ji-1;j1;j--)
{
if(wordDict.contains(s.substring(j))dp[j-1])
{
dp[i]true;
continue;
}
//上面两个条件均不成立表明dp[i]无法进行划分
dp[i]false;
}}
return dp[s.length()-1];
}
递归求解
public Boolean stringPartition2(String s,ListStringwordDict,int index)
{
//表示到了最后一步了前面已经成功了
if(indexs.length())
{
return true;
}
Boolean flagfalse;
//index之前已经可以构成子串从index开始寻找
for(int iindex;is.length();i)
{
if(wordDict.contains(s.substring(index,i1)))
{
flagflag||stringPartition2(s,wordDict,i1);
}
}
return flag;
}
