139. Word Break

Problem Statement

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 <= 300
1 <= wordDict.length <= 1000
1 <= wordDict[i].length <= 20
s and wordDict[i] consist of only lowercase English letters.
All the strings of wordDict are unique.

Intuition

Loop through the string 
If left partition is infact in dictionary then
Check for right partition if that returns true

Links

https://leetcode.com/problems/word-break/description/

Video Links

Approach 1:

Memoization

C++

class Solution {
public:
    unordered_map<string, bool> dp;

    bool find_ans(string s, unordered_map<string, bool> &dict){
        if(dict.find(s) != dict.end())
            return true;

        if(dp.find(s) != dp.end())
            return dp[s];

        for(int i=0; i<s.size(); i++){
            string left = s.substr(0,i+1);
            string right = s.substr(i+1);

            if(dict.find(left) != dict.end()){
                bool temp = find_ans(right, dict);

                if(temp == true){
                    // Memoize the string
                    dp[s] = true;
                    return true;
                }
            }
        }

        dp[s] = false; 
        /*
        This is to save that taking this sub-string does not give us the answer
        */
        return false;
    }


    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<string, bool> dict; 

        for(auto &it: wordDict)
            dict[it] = true;

        return find_ans(s, dict);
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++