本文主要是介绍动态规划---单词拆分,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s
则返回 true
。
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
思路:本题属于完全背包问题,字符串s的长度为背包容量,字符串列表wordDict中的每一个元素相当于物品。
动态规划五部曲:
1.确定dp数组及含义
dp数组为元素类型是布尔型的一维数组,dp[i]代表长度为i的字符串可否由字符串列表里的元素拼成。
2.确定递推公式
如果dp[j]=true,j<i,且在[j,i]这个区间的子串出现在字典里,那么dp[i]=true
3.dp数组初始化
dp[0]=true,其他为false
4.确定遍历顺序
本题我们求的属于排列数,因为用字典中的元素凑成字符串是有顺序的。因此遍历顺序为先遍历背包(字符串),再遍历物品(字符串列表)。
5.举例推导dp数组
s="leetcode",wordDict=["leet","code"]
dp=[1,0,0,0,1,0,0,0,1]
代码:
public boolean wordBreak(String s, List<String> wordDict) {HashSet<String> set=new HashSet<>(wordDict);boolean[] dp=new boolean[s.length()+1];dp[0]=true;for(int i=1;i<=s.length();i++){for(int j=0;j<i&&!dp[i];j++){if(set.contains(s.substring(j,i))&&dp[j])dp[i]=true;}}return dp[s.length()];}
这篇关于动态规划---单词拆分的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!