LeetCode [139] Word Break

 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; } };