LintCode 107 给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。

本文主要是介绍LintCode 107 给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

代码一、使用递归算法，超时

class Solution {
public:/** @param s: A string* @param dict: A dictionary of words dict* @return: A boolean*/bool wordBreak(string &s, unordered_set<string> &dict) {// write your code herereturn dp(s,dict,0);}bool dp(string &s,unordered_set<string> &dict,int p){bool ans=false;if(p==s.size()) return true;for(int i=p;i<s.size();i++){if(dict.count(s.substr(p,i-p+1))!=0) ans=max(ans,dp(s,dict,i+1));}return ans;}
};

代码二、暴力破解双重循环O(n平方)，超时

class Solution {
public:/** @param s: A string* @param dict: A dictionary of words dict* @return: A boolean*/bool wordBreak(string &s, unordered_set<string> &dict) {// write

这篇关于LintCode 107 给定字符串 s 和单词字典 dict，确定 s 是否可以分成一个或多个以空格分隔的子串，并且这些子串都在字典中存在。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---