Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can be segmented as "leet code".
给定字符串，以及一个字典，判断字符串是否能够拆分为字段中的单词。例如，字段为{hello，world}，字符串为hellohelloworld，则可以拆分为hello,hello,world，都是字典中的单词。
这个题目唤作“分词问题”，略显宽泛。只是想提及这个问题，这是在自然语言处理，搜索引擎等等领域中，非常基础的一个问题，解决的方法也比较多，相对比较成熟，不过这仍旧是一个值得进一步探索的问题。那我们先从这个简单的题目入手，看看如何处理题目中这个问题。 最直接的思路就是递归，很简单。我们考虑每一个前缀，是否在字典中？如果在，则递归处理剩下的字串，如果不在；则考虑其他前缀。示例代码如下：
#include<iostream> #include<unordered_set> #include<string> using namespace std; class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { int len=s.length(); if(len==0) return true; int i; for(i=1;i<=len;i++) { if(dict.count(s.substr(0,i))>0&&wordBreak(s.substr(i,len-i),dict)) return true; } return false; } }; int main() { unordered_set<string> dict={"aaaa","aaa"}; Solution s; string ss="aaaaaa"; cout<<s.wordBreak(ss,dict)<<endl; }
在上面的代码中：每一种情况都要处理substr，程序的耗时比较长，如果在OJ上提交，干脆超时的，那么如何改进呢？
这个题目的处理，上期的题目是很相似的。在递归子问题中，找重复的子问题。也非常明显，如下图(图片来自GeeksforGeeks)所示：
所以，通过动态规划的方法，可以通过有较大幅度的提升，同样，这个题目与前面的每一个状态都有关系的，所以，是一个二重循环，时间复杂度为O(n^2)。示例代码如下：
#include<iostream> #include<unordered_set> #include<string> #include<cstring> using namespace std; class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { int len=s.length(); if(len==0) return true; bool dp[len+1]; memset(dp,0,sizeof(dp)); int i,j; for(i=1; i<=len; i++) { if(dp[i]==false&&dict.count(s.substr(0,i))>0) dp[i]=true; if(i==len&&dp[i]==true) return true; if(dp[i]==true) { for(j=i+1; j<=len; j++) { if(dp[j]==false&&dict.count(s.substr(i,j-i))>0) dp[j]=true; if(j==len&&dp[j]==true) return true; } } } return false; } }; int main() { unordered_set<string> dict= {"leet","code"}; Solution s; string ss = "leetcode"; cout<<s.wordBreak(ss,dict)<<endl; }
方法三：
// 第二版 参考leetcode官网上的答案 class Solution { public: bool wordBreak(string s, unordered_set<string> &dict) { vector<bool> wordB(s.length() + 1, false); wordB[0] = true; for (int i = 1; i < s.length() + 1; i++) { for (int j = i - 1; j >= 0; j--) { if (wordB[j] && dict.find(s.substr(j, i - j)) != dict.end()) { wordB[i] = true; break; //只要找到一种切分方式就说明长度为i的单词可以成功切分，因此可以跳出内层循环。 } } } return wordB[s.length()]; } };
微信关注我们
转载内容版权归作者及来源网站所有！
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。
马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。
为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。
Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。
扫码在手机上查看文章
扫描二维码，手机阅读更方便
有任何问题或合作意向欢迎联系我们
Email: 99873273@qq.com
QQ: 99873273