知识点
相关文章
更多最近更新
更多LeetCode:Word Break(DP)
2019-03-02 00:53|来源: 网路
题目地址:http://oj.leetcode.com/problems/word-break/
简单的动态规划问题,采用自顶向下的备忘录方法,代码如下:
1 class Solution { 2 public: 3 bool dictContain(unordered_set<string> &dict, string s) 4 { 5 unordered_set<string>::iterator ite = dict.find(s); 6 if(ite != dict.end()) 7 return true; 8 else return false; 9 } 10 11 bool wordBreak(string s, unordered_set<string> &dict) 12 { 13 // Note: The Solution object is instantiated only once and is reused by each test case. 14 if(dict.empty()) 15 return false; 16 const int len = s.size(); 17 bool canBreak[len]; //canBreak[i] = true 表示s[0~i]是否能break 18 memset(canBreak, 0, sizeof(bool)*len); 19 for(int i = 1; i <= len; i++) 20 { 21 if(canBreak[i-1] == false && dictContain(dict, s.substr(0, i))) 22 canBreak[i-1] = true; 23 24 if(canBreak[i-1] == true) 25 { 26 if(i == len)return true; 27 for(int j = 1; j <= len - i; j++) 28 { 29 if(canBreak[j+i-1] == false && dictContain(dict,s.substr(i, j))) 30 canBreak[j+i-1] = true; 31 32 if(j == len - i && canBreak[j+i-1] == true)return true; 33 34 } 35 } 36 37 } 38 39 return false; 40 } 41 42 43 };
注意:在本机调试时,编译器要开启c++11支持,因为#include<unordered_set>是c++11的标准
相关参考资料
微信公共账号“待字闺中”也有关于此题的讨论:请点击 这里 或 这里
【版权声明】转载请注明出处:http://www.cnblogs.com/TenosDoIt/p/3384853.html
转自:http://www.cnblogs.com/TenosDoIt/p/3384853
相关问答
更多-
Leetcode中的完美广场(Perfect Square in Leetcode)[2021-09-21]
您提到的解决方案是该算法的自底向上版本。 为了更好地理解算法,我建议查看解决方案的自顶向下版本。 让我们仔细看看计算包含在数字N内的最小量的完美平方的递归关系。 对于给定的N和任意任意数x (这是候选人被认为是最短序列数的成员,其完美平方总和为N ): f(N, x) = 0 , if N = 0 ; f(N, x) = min( f(N, x + 1), f(N - x^2, 1) ) , if N >= x^2 ; f(N, x) = ... -
什么让
只在break-word失败时才打破?(How to let only break-all when break-word fails?)[2023-12-10] 没有直接的HTML或CSS方法来做到这一点。 但是,你可能会过度使用并使用javascript解决方案。 一种策略:估计适合表格单元格的一行中的最大字符数,在表格单元格中搜索长于该数字的单个单词的字符串,并在单词中插入标签(或连字符)它,或者在那一点上添加空格等。 $('td').each(function() { var contents = $(this).html(); contents = contents.replace(/(\w{25})/g,"$1 "); ... 如果你想只在行尾打破这个词,那就用吧 word-break: break-all; 而不是突破口。希望这会有所帮助。 在这里演示 If you want to break the word only at the end of the line then use word-break: break-all; rather then break-word.. Hope this will help. Demo hereword-break:break-all its break the sentence and text in other line word-wrap:break-word它不会中断句子它的中断和整句不会中断地跳到下一行 p { width:100px; word-break:break-all; padding-left:20px; } div { width:100px; word-wrap: break-word; padding-left:20px; } ...Leetcode:最大矩形(Leetcode: Maximal rectangle)[2022-08-27]
您的算法中存在错误: while (j < col && matrix[i][j] == '1') { Rect *rect = &rectab[i][j]; if (el < rect->l) el = rect->l; if (er > rect->r) er = rect->r; if (et < rect->t) et = rect->t; if (eb > rec ...trees[n]是具有正好n节点的树的数量。 有1棵树有0个节点,因此trees[0] == 1 。 对于给定的n > 0存在根节点和两个子树,其总大小为: n-1 trees[n-1]左边的可能树和右边的trees[0] trees[n-2]左边的可能树和右边的trees[1] ... trees[1]左侧可能的树和右侧的trees[n-1-1] trees[0]可能的树木在左边, trees[n-1]在右边 当左侧有trees[k] ,右侧有trees[l]时, trees[k]*trees[l]可能的 ...虽然我确实认为你不需要display: flex in .item ,但以下内容适用于各种浏览器: .item { display: flex; flex-direction: column; width: 33vw; word-break: break-word; /* Chrome, Safari */ word-wrap: break-word; /* IE11, Firefox */ } 为什么这样做? 简单地说flex-direction: column强制flex块尊重元素 ...LeetCode排序颜色java(LeetCode sort color java)[2022-05-29]
检查API due Collections.sort import java.util.Arrays; import java.util.Collections; import java.util.List; public class Main { public static void main(String[] args) { //Must be Integer class Integer[] nums = { 1, 2, 3, 0, 1, 2, 3, 1, 4, 4, 4, 0, 0 ...LeetCode上的两个和(Two Sum on LeetCode)[2023-10-20]
def twosum(nums=(6, 7, 11, 15, 3, 6, 5, 3), target=6): lookup = dict(((v, i) for i, v in enumerate(nums))) return next(( (i+1, lookup.get(target-v)+1) for i, v in enumerate(nums) if lookup.get(target-v, i) != i), None) ...我知道你说你想避免
,但有.. jsfiddle演示 用法示例: some random text and stuff sales/tele
如果你重新调整p的大小,那么这个词在远程后会中断。 见MDN 遗憾的是,对marketing some more words here 支持有限,因为IE10不支持。 我只想到一个随机的CSS替代品.. jsFiddle演示 HTML some random text and stuff sales/