当前位置：首页 > news >正文

濮阳网站建设熊掌网络网站的特点有那些

news 2025/10/12 5:03:05

濮阳网站建设熊掌网络,网站的特点有那些,最好的外贸网站建设,搞笑图片网站源码题意：给定一个string以及一个wordDict,要求返回一个vector<string> ，这个vector中的string都是word Dict中的组合 Input: s “catsanddog”, wordDict [“cat”,“cats”,“and”,“sand”,“dog”] Output: [“cats and dog”,“cat sand dog”…

题意：给定一个string以及一个wordDict,要求返回一个vector<string> ，这个vector中的string都是word Dict中的组合

Input: s = “catsanddog”, wordDict = [“cat”,“cats”,“and”,“sand”,“dog”]
Output: [“cats and dog”,“cat sand dog”]

想法：backtracking, 想象一下每一轮你要干什么，首先拿wordDict中的每个单词去填写，如果对不上号，你就填下一个单词直到最后填到单词末尾就结束了。

class Solution {
public:vector<string> ret;vector<string> wordBreak(string s, vector<string>& wordDict) {dfs(s, "", 0 , wordDict);return ret;}void dfs(string& s, string cur, int st, vector<string>& wordDict) {if (st == s.size()) {cur.pop_back();ret.push_back(cur);}for(auto word : wordDict) {if(st + word.size() <= s.size()) {if(word == s.substr(st, word.size())) {string temp = cur;cur += word;cur += " ";dfs(s, cur, st+word.size(), wordDict);cur = temp;}}}}
};