最好网站设计案例,做网站应该会什么软件,wordpress 反向代理 配置,沈阳网站建设索王道下拉单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意#xff1a;不要求字典中出现的单词全部都使用#xff0c;并且字典中的单词可以重复使用。
示例 1#xff1a;
输入: s “leetcode”, wordDict …单词拆分 给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
注意不要求字典中出现的单词全部都使用并且字典中的单词可以重复使用。
示例 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
class Solution {
public:bool wordBreak(string s, vectorstring wordDict) {vectorbool dp(s.size() 1, false);dp[0] true;unordered_setstring us;for(auto d: wordDict) {us.insert(d);}for(int i 1; i s.size(); i) {for(int j 0; j i; j) {if(dp[j] us.find(s.substr(j, i-j)) ! us.end()) {dp[i] true;break;}}}return dp[s.length()];}
};
