139. Word Break
Medium
Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.
Example 1:
Input: s = "leetcode", wordDict = ["leet", "code"] Output: true Explanation: Return true because"leetcode"
can be segmented as"leet code"
.
Example 2:
Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: true Explanation: Return true because"
applepenapple"
can be segmented as"
apple pen apple"
. Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: false
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public: bool wordBreak(string s, vector<string>& wordDict) { unordered_set<string> set(wordDict.begin(), wordDict.end()); int n = s.size(); vector<bool> dp(n+1, false); dp[0] = true; for(int i=1; i<=n; ++i){ for(int j=0; j<i; ++j){ if(dp[j] && set.count(s.substr(j, i-j))==1){ dp[i] = true; break; } } } return dp[n]; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | class Solution { public: bool wordBreak(string s, unordered_set<string>& wordDict) { queue<int> que; int n = s.size(); que.push(0); unordered_set<int> visited; while(!que.empty()){ int start = que.front(); que.pop(); for(int end = start; end<n; end++){ string word = s.substr(start, end-start+1); if(wordDict.count(word)){ if(end+1==n) return true; if(visited.count(end+1)==0){ que.push(end+1); visited.insert(end+1); } } } } return false; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | class Solution { public: bool wordBreak(string s, unordered_set<string>& wordDict) { int n = s.size(); vector<bool> visited(n, false); return dfs(s, n, 0, wordDict, visited); } bool dfs(string s, int n, int pos, unordered_set<string> & wordDict, vector<bool> &visited){ visited[pos] = true; if(pos==n){ return true; }else{ for(int i=pos; i<n; ++i){ string word = s.substr(pos, i-pos+1); if(wordDict.count(word)){ if(!visited[i+1]){ if(dfs(s, n, i+1, wordDict, visited)) return true; } } } } return false; } }; |
No comments:
Post a Comment