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
Solution : (Bottom Up DP)
classSolution{public:boolwordBreak(string s,vector<string> &wordDict) {int n =s.length(); unordered_set<string> st;for (int i =0; i <wordDict.size(); i++) {st.insert(wordDict[i]); } vector<vector<int>>v(n,vector<int>(n,-1)); //Store length of substrfor (int k =1; k <= n; k++) { //Check for all substrfor (int i =0; i < n - k +1; i++) { string str =s.substr(i, k);if (st.find(str) !=st.end()) {v[i][i + k -1] =1;continue; }else { //Split and checkfor (int j = i+1; j < i + k; j++) {if (v[i][j-1] !=-1&&v[j][i + k -1] !=-1) {v[i][i + k -1] =1;break; } } } } }if (v[0][n -1] ==-1) {returnfalse; }returntrue; }};