139.單詞拆分
給定一個非空字元串 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 解題思路：
深度優先搜尋（DFS），動态規劃（DP），字元串哈希。
1. 字元串wordDict進入哈希表。這裡可以用unorderded_map來實作比較友善。期間還可以統計單詞的最小長度min和最大長度max。
2. 從pos=0開始處搜尋，查找長度為[min,max]的子串，max還要根據s的規模确定是否溢出。每得到一個單詞在map中出現，就遞歸。
3. 為了防止已經搜尋的路徑重複搜尋，應該建立bool dp[10001]，儲存已經通路過的路徑。
| class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { int size = wordDict.size(), i; if (size == 0) return false; ss = s; for (i = 1; i <= size; i++) { mp[wordDict[i - 1]] = true; if (int(wordDict[i - 1].size()) > max) max = int(wordDict[i - 1].size()); if (int(wordDict[i - 1].size()) < min) min = int(wordDict[i - 1].size()); } length = s.size(); if (length == 0) return false; return DFS(0); } bool DFS(int pos) { if (pos == length) return true; int left = min, right = max; if (right + pos - 1 >= length) right = length - pos; string str; bool sgn; for (int i = left; i <= right; i++) { str = ss.substr(pos, i); if (mp[str] == true) { if (dp[pos + i] != 0) { sgn = (dp[pos + i] == -1 ? false : true); } else { sgn = DFS(pos + i); dp[pos + i] = (sgn == true ? 1 : -1); } if (sgn == true) return true; } else { mp.erase(str); } } return false; } private: int dp[10001]; unordered_map<string, bool> mp; int max = 0, min = INT32_MAX; int length; string ss; }; |
140.單詞拆分II
給定一個非空字元串 s 和一個包含非空單詞清單的字典 wordDict，在字元串中增加空格來建構一個句子，使得句子中所有的單詞都在詞典中。傳回所有這些可能的句子。
說明：
- 分隔時可以重複使用字典中的單詞。
- 你可以假設字典中沒有重複的單詞。
示例 1：
輸入:
s = " catsanddog "
wordDict = ["cat", "cats", "and", "sand", "dog"]
輸出:
[
"cats and dog",
"cat sand dog"
] 示例 2：
輸入:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
輸出:
[
"pine apple pen apple",
"pineapple pen apple",
"pine applepen apple"
]
解釋: 注意你可以重複使用字典中的單詞。
示例 3：
輸入:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
輸出:
[] 解題思路：
和139一緻，隻不過要儲存每一種搜尋的結果。
| class Solution { public: vector<string> wordBreak(string s, vector<string>& wordDict) { int size = wordDict.size(), i; if (size == 0) return{}; ss = s; for (i = 1; i <= size; i++) { mp[wordDict[i - 1]] = true; if (int(wordDict[i - 1].size()) > max) max = int(wordDict[i - 1].size()); if (int(wordDict[i - 1].size()) < min) min = int(wordDict[i - 1].size()); } length = s.size(); if (length == 0) return{}; vector<string> res = DFS(0); return res; } vector<string> DFS(int pos) { visit[pos] = true; if (pos >= length) { dp[pos].push_back(""); return{ "" }; } int left = min, right = max; if (right + pos - 1 >= length) right = length - pos; string str, sgn, str1; vector<string> vs; for (int i = left; i <= right; i++) { str = ss.substr(pos, i); if (mp[str] == true) { int size = dp[pos + i].size(); if (visit[pos+i] == true) { vs = dp[pos + i]; } else { vs = DFS(pos + i); } for (int j = 1; j <= int(vs.size()); j++) { if (vs[j - 1] == "") { dp[pos].push_back(str); } else dp[pos].push_back(str +" "+ vs[j - 1]); } } else mp.erase(str); } return dp[pos]; } private: vector<string> dp[10001]; bool visit[10001]; unordered_map<string, bool> mp; int max = 0, min = INT32_MAX; int length; string ss; }; |