17.Word Break

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)

class Solution
{
public:
    bool wordBreak(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 substr
        for (int k = 1; k <= n; k++)
        {
            //Check for all substr
            for (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 check
                    for (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)
        {
            return false;
        }
        return true;
    }
};

Space Complexity: O(2n) Time Complexity: O(n^2)