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++

Similar Problems