Word Break

Leetcode 139: Word Break

Problem

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

C++ Code

class Solution {
public:
    
    bool rec(string& s, set<string>& all_words, int begin_index, vector<int>& memo){
        if(begin_index == s.length()) //we reached end of the string, that means, whatever words we found so far, matched with any of the dictionary words
            return true;
        
        if(memo[begin_index] != -1) //that means, we came to this index before and know the result is either 0 or 1
            return memo[begin_index];
        
        for(int cur_index = begin_index + 1; cur_index <= s.length(); cur_index++){
            //Now, we will make words of 1, 2, 3....n characters beginning from begin index
            string cur_word = s.substr(begin_index, cur_index - begin_index);
            //Then we will check if this word is a dictionary word or not
            if(all_words.find(cur_word) != all_words.end()){
                /* When this length of word belongs to the dictionary word, we don't need to check anything for it. So we will call the recursion passing ending index as the beginning
index and see if we can find a dictionary word from the next constructed words. This way, if we continue to keep finding, the function will reach its terminate condition after some time. But, if we do not reach the terminate condition, we will come back to this loop eventually and create a new cur_word with the next length and call the recursion again.*/
                if(rec(s, all_words, cur_index, memo) == true)
                    return memo[begin_index] = true;
            }
        }
        return memo[begin_index] = false;
    }
    
    bool wordBreak(string s, vector<string>& wordDict) {
        //set of all words is generated here
        set<string> all_words(wordDict.begin(), wordDict.end());
        /*
        we will use a memoization table to keep track of
        an index is used or not. By used, we mean that, starting from this
        index, we found a word and that word is used.
        If it is not used yet, -1 is assigned for that
        If it is used, but we didn't find any result, we put 0
        If it is used, but we found any result, we put 1
        */
        vector<int> memo(s.length(), -1);
        
        return rec(s, all_words, 0, memo);
    }
};