当前位置: 首页> 游戏> 单机 > 西安企业网站建设多少钱_私人信息调查_免费推广软件平台_谷歌推广怎么操作

西安企业网站建设多少钱_私人信息调查_免费推广软件平台_谷歌推广怎么操作

时间:2025/7/10 17:48:36来源:https://blog.csdn.net/visitorcsdn/article/details/145560257 浏览次数:0次
西安企业网站建设多少钱_私人信息调查_免费推广软件平台_谷歌推广怎么操作

动态规划,字符串截取,可重复用,集合类。

题目

单词可以重复使用,一个单词可用多次,应该是比较灵活的组合形式了,可以想到用dp,遍历完单词后的状态的返回值。而这里的wordDict给出的是list,但可以用set,因为hashset可以去重,hashset的查找比list要快。然后就是这里的额dp数组是个boolean值,然后用截取字符串的形式去看set里能不能找到,找不到说明拼不了。

时间复杂度:O(n^2) ,空间复杂度:O(n) 。

public class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> w = 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; j++) {if (dp[j] && w.contains(s.substring(j, i))) {dp[i] = true;//能找到break;}}}return dp[s.length()];//遍历到最后一个字符时这个单词的状态}
}

状态维护,boolean类型很适合做标记位。

 

关键字:西安企业网站建设多少钱_私人信息调查_免费推广软件平台_谷歌推广怎么操作

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: