一般制作一个网站要多久,百度seo排名优化排行,wordpress+下载受限,三网合一 网站给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。
示例 1#xff1a; 输入: s “leetcode”, wordDic…给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 1 输入: s “leetcode”, wordDict [“leet”, “code”] 输出: true 解释: 返回 true 因为 “leetcode” 可以由 “leet” 和 “code” 拼接成。
示例 2 输入: s “applepenapple”, wordDict [“apple”, “pen”] 输出: true 解释: 返回 true 因为 “applepenapple” 可以由 “apple” “pen” “apple” 拼接成。 注意你可以重复使用字典中的单词。
示例 3 输入: s “catsandog”, wordDict [“cats”, “dog”, “sand”, “and”, “cat”] 输出: false
提示 1 s.length 300 1 wordDict.length 1000 1 wordDict[i].length 20 s 和 wordDict[i] 仅由小写英文字母组成 wordDict 中的所有字符串 互不相同
动态规划
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {unordered_setstring wordDictSet;for(auto word : wordDict){wordDictSet.insert(word);}vectorbool dp(s.size()1);dp[0] true;for(int i 1; i s.size(); i){for(int j 0; j i; j){if(dp[j] wordDictSet.find(s.substr(j, i-j)) ! wordDictSet.end()){dp[i] true;break;}}}return dp[s.size()];}
};时间复杂度O(n^2) 空间复杂度O(n)
这道题我们首先定义一个unordered_set来储存字典里的单词这样有利于快速查找。然后我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0…i−1] 是否能被空格拆分成若干个字典中出现的单词。我们首先在外层循环遍历i代表着遍历字符串然后内层循环j的作用是来判断该字符串前j个字符组成的字符串能否被拆分成字典里的单词并且判断第j1个字符后的单词是否在字典里。这时候我们利用到了find操作当find找不到字典里对应单词的时候就会指向wordDictSet的end那么只要当指针不指向end则说明在字典里有对应单词。
最后返回dp[s.size()]即可。
