Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words. For example, given s = "leetcode", dict = ["leet", "code"]. Return true because "leetcode" can be segmented as "leet code".
public class Solution { // shoudl consider input, wordDict is small, check through string s // O(n*m) m for small Dict public boolean wordBreak(String s, ListwordDict) { boolean[] canBreak = new boolean[s.length() + 1]; // s can be break from start to i; canBreak[0] = true; for(int i=0; i<= s.length(); i++){ if(!canBreak[i]) continue; for(String word : wordDict) { // renew each possible position with true int len = word.length(); int end = i + len; // those unreachable position and reached position should ignore if(end > s.length() || canBreak[end]) continue; if(s.substring(i,end).equals(word)){ canBreak[end] = true; } } } return canBreak[s.length()]; } }
/* //Second DP put listinto Set O(n^2) time two nested for loop O(K) for Dict for(int i=1; i <= s.length(); i++){ // fix the ending, find the starting, then compare middle for(int j=0; j < i; j++){ if(f[j] && dict.contains(s.substring(j, i))){ f[i] = true; break; } } } */
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/69994.html
摘要:理解和的区别从易于区分和理解的角度,我引用了无双在你真的了解和的区别吗一文中对两个属性作用的解释属性用来标明是否允许浏览器在单词内进行断句,这是为了防止当一个字符串太长而找不到它的自然断句点时产生溢出现象。 white-space 、 word-wrap 和 word-break 是决定段落中的文本如何展示的3个css属性,属性说明请点击链接查看参考手册。 white-space wh...
摘要:英文换行来到英文,情况就要复杂一些。在英文中有单词的概念,所以在换行时就得考虑单词的完整性。上面介绍的值,主要也是针对英文的,汉字还是按照浏览器的默认行为,装不下就换行。最后显示时,英文还是按照默认行为,中文变成了不换行。 上一篇博客中介绍white-space属性时聊到了换行,这一篇介绍换行的细节。 浏览器的默认行为 浏览器的换行行为,对于中文和英文存在一些差别。 中文换行 正如上一...
我们可能在很多地方如 README 文件、Makefile 文件以及 Dockerfile 文件中看到GO111MODULE=on, 对于刚接触的Golang的开发者可能对此有很多疑惑。这片文章,我将详细介绍GO111MODULE变量的意义,以及什么时候需要使用到该变量, 同时也总结了一些在使用 Go Modules 时需要注意的细节,帮助你在下次遇到这个变量时不再疑惑。GO111MODULE=o...
ChatGPT和Sora等AI大模型应用,将AI大模型和算力需求的热度不断带上新的台阶。哪里可以获得廉价算力,进行AI视频生成等模型开发和应用呢?Compshare是隶属于UCloud云计算的GPU算力平台,专注提供高性价比的NVIDIA RTX 40 系列资源,满足 AI应用、模型推理/微调、科学计算等多场景需要。UCloud本身是一家专注于公有云的云计算厂商,成立于2012年,是中国第一家科创...
阅读 2209·2021-11-22 15:29
阅读 4098·2021-11-04 16:13
阅读 991·2019-08-29 16:58
阅读 339·2019-08-29 16:08
阅读 1457·2019-08-23 17:56
阅读 2378·2019-08-23 17:06
阅读 3166·2019-08-23 16:55
阅读 2058·2019-08-23 16:22