【算法题】word-break-ii àì夳堔傛蜴生んèń 2022-06-05 02:40 71阅读 0赞 此题是word-break的follow up,word-break用中规中矩的dp算法即可解决。 这个需要打印所有解决方案。 我用dp + dfs, leetcode和lintcode都可以通过。 时间复杂度:O(n方) 空间复杂度:O(n方) 题目: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words. Return all such possible sentences. For example, given s = `"catsanddog"`, dict = `["cat", "cats", "and", "sand", "dog"]`. A solution is `["cats and dog", "cat sand dog"]`. 我的代码: class Solution { public: vector<string> res; vector<vector<int>> dp; vector<string> wordBreak(string s, vector<string> &wordDict) { // write your code here if (s.size() == 0 || wordDict.size() == 0) { return res; } int maxLength = 0; for (auto w : wordDict) { maxLength = max(maxLength, (int)w.size()); } for (int i = 0; i < s.size() + 1; i++) { dp.push_back(vector<int>()); } dp[0].push_back(0); for (int i = 1; i < s.size() + 1; i++) { for (int j = 1; j <= i && j <= maxLength; j++) { if (dp[i - j].size() != 0 && find(wordDict.begin(), wordDict.end(), s.substr(i - j, j)) != wordDict.end()) { dp[i].push_back(i - j); } } } for (int i = 0; i < dp[s.size()].size(); i++) { string res_element = ""; help(s, res_element, s.size(), dp[s.size()][i]); } return res; } void help(string s, string res_element, int pos, int last_pos) { if (last_pos == 0) { res_element = s.substr(0, pos) + " " + res_element; res_element = res_element.substr(0, res_element.size() - 1); res.push_back(res_element); return; } if (dp[last_pos].size() == 0) { return; } res_element = s.substr(last_pos, pos - last_pos) +" " + res_element; for (auto lp : dp[last_pos]) { help(s, res_element, last_pos, lp); } return; } };
相关 算法题刷题笔记 在线题库 > [牛客华为机试题库【题号 HJ开头】(重点看)][HJ] > [牛客在线编程算法篇【题号NC开头】][NC] > [剑指offer【题号 JZ开头】 深藏阁楼爱情的钟/ 2024年03月27日 11:33/ 0 赞/ 33 阅读
相关 算法数组题 1.用最少的代码求出三个数那个数最大 <?php $a=10;$b=4;$c=22; $max=($a>$b?$a:$b)>$c?($a>$b?$a: 分手后的思念是犯贱/ 2022年08月22日 12:30/ 0 赞/ 107 阅读
相关 算法题总结 二、数据结构和算法 1.使对象可以像数组一样进行foreach循环,要求属性必须是私有。(Iterator模式的PHP5实现,写一类实现Iterator接口)( 我就是我/ 2022年06月11日 07:28/ 0 赞/ 122 阅读
相关 算法题 上学时学过的算法,青山遮不住,毕竟东流去,都忘得差不多了。。。。 题目1:使用一个数组实现一个循环队列 分析:简单来讲就是用一个数组,实现个队列的功能,可以用两个脚标来控制 我就是我/ 2022年06月10日 07:19/ 0 赞/ 121 阅读
相关 算法题分析 【题目描述】 在主城站街很久之后,小萌决定不能就这样的浪费时间虚度青春,他打算去打副本。 这次的副本只有一个BOSS,而且BOSS是不需要击杀的,只需要和它比智力……. ╰半橙微兮°/ 2022年06月05日 03:20/ 0 赞/ 126 阅读
相关 算法题1 假设有这样一个国家,其法律规定当公民月收入为x时,若x> 1.则每月应当缴纳的税金为x的因数中除了x之外的最大值:同时该国法律允许公民将月收入分成若干部分(每部分均为整数),要 野性酷女/ 2022年05月08日 18:24/ 0 赞/ 115 阅读
相关 算法逻辑题 目录 统计一个txt文本文件中字母和数字的数量 获取数值数组中第二大的数的索引值,例如:数值数组为 \{2,5,8,8,3,7,9,4,1,6,9\}, 结果为 2 两 古城微笑少年丶/ 2022年02月23日 04:20/ 0 赞/ 142 阅读
相关 算法题 <table> <tbody> <tr> <td>N.RSA加密算法</td> </tr> <tr> <td> <table> 桃扇骨/ 2022年01月10日 10:23/ 0 赞/ 160 阅读
相关 其他算法题 绳子可以覆盖的最多点数 数轴上从左到右有n各点a\[0\], a\[1\], ……,a\[n -1\],给定一根长度为L的绳子,求绳子最多能覆盖其中的几个点 题解:对于 末蓝、/ 2021年09月18日 12:54/ 0 赞/ 275 阅读
还没有评论,来说两句吧...