Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
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
Constraints:
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20sandwordDict[i]consist of only lowercase English letters.- All the strings of
wordDictare unique.
DP with another approach.
bool wordBreak(string s, vector<string>& wordDict) {
vector<bool> dp(s.size()+1, false);
dp[0] = true;
// we mark as true every index that we managed to segment so far
for (int i = 1; i <= s.size(); i++)
for (int j = 0; j < i; j++)
if ((dp[j]) && (find(wordDict.begin(), wordDict.end(), s.substr(j, i-j)) != wordDict.end())) {
dp[i] = true;
break;
}
return dp.back();
}Here, we need to consider dp[0] which acts as base case. And, for all words in s, we would find if the word is existing in wordDict. Hence, this sums up to s.size() + 1.
This dp array will be helpful in segmenting.
For example,
"catsandog"
["cats","dog","sand","and","cat"]
Output : False
The DP array would be :
dp[0] 0,
dp[1] 0(c),
dp[2] 0(a),
dp[3] 1(t),
dp[4] 1(s),
dp[5] 0(a),
dp[6] 0(n),
dp[7] 1(d),
dp[8] 0(o),
dp[9] 0(g)
Initially dp[0] is set to true. So, substrings are considered from 0th position.
1. The program first looks into the letter "c" in s and checks if there is matching word in wordDict from the substring s[0]. Since there is no match, dp[1] will be set to 'false'. - s[0] - c
2. It goes to the next letter 'a'. Since there is no match in wordDict from the substring s[0-1], dp[2] is set to 'false'. - s[0-1] - ca
3. It goes to the next letter 't'. There is a match found in wordDict from the substring s[0-2], so dp[3] is set to 'true'. - s[0-2] - cat
Now, the second substring also will be considered from position 3 in s.
4. It goes to the next letter 's'. There is a match found in wordDict from the substrings s[0-3], s[3], so dp[4] is set to 'true' - - s[0-3] - cats, s[3] - s
Now, the third substring also will be considered from position 4 in s.
5. It goes to the next letter 'a'. Since there is no match in wordDict from the substrings s[0-4] s[3-4] s[4], dp[5] is set to 'false'. - s[0-5] - catsa, s[3-4] - sa, s[4] - a
6. It goes to the next letter 'n'. Since there is no match in wordDict from the substrings s[0-5] s[3-5] s[4-5], dp[6] is set to 'false'. - s[0-6] - catsan, s[3-5] - san, s[4-5] - an
7. It goes to the next letter 'd'. There is a match found in wordDict from the substrings s[0-6], s[3-6] s[4-6], so dp[7] is set to 'true' - - s[0-7] - catsand, s[3-6] - sand, s[4-6] - and
8. It goes to the next letter 'o'. Since there is no match in wordDict from the substrings s[0-7] s[3-7] s[4-7], s[7], dp[8] is set to 'false'. - s[0-7] - catsando, s[3-7] - sando, s[4-7] - ando, s[7] - o
9. It goes to the next letter 'g'. Since there is no match in wordDict from the substrings s[0-8] s[3-8] s[4-8], s[7-8], dp[9] is set to 'false'. - s[0-8] - catsandog, s[3-8] - sandog, s[4-8] - andog, s[8] - og
At this point, the last two letter left hung, and it is not segmented meaningfully. string s is not fully segmented.
cat | sand | og
cats | and | og
"catsandog"
["cats","dog", "an","cat"]
Output : True
cats | an |dog
Comments
Post a Comment