leetcode 序列重排，[leetcode] 140. 單詞拆分 II

2023-11-18 阅读 29 评论 0

摘要：class Solution {int n;vector<string>res;unordered_map<int,set<int>>hash;string s;void dfs(int start, string temp){if(start == n){res.push_back(temp);return ;}for(auto end : hash[start]){if(start == 0){//前面不要有空格dfs

在這里插入圖片描述

class Solution {int n;vector<string>res;unordered_map<int,set<int>>hash;string s;void dfs(int start, string temp){if(start == n){res.push_back(temp);return ;}for(auto end : hash[start]){if(start == 0){//前面不要有空格dfs(end, s.substr(start, end - start));}else{dfs(end, temp +" " + s.substr(start, end - start));}}}
public:vector<string> wordBreak(string s, vector<string>& wordDict) {this->n = s.size();this->s = s;unordered_set<string>m_set(wordDict.begin(), wordDict.end());vector<bool>dp(s.size() + 1, false);dp[s.size()] = true;for(int i = s.size(); i >= 1; i--){if(dp[i] == true){for(int j = 0; j < i; j++){if(m_set.count(s.substr(j, i - j)) == 1){hash[j].insert(i);dp[j] = true;}}}}dfs(0, "");return res;}
};