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

Problem Link

Word Break - LeetCode

Reference Videos

https://www.youtube.com/watch?v=WepWFGxiwRs

Code

Using DP (LT Accepted)

class Solution {
public:
    bool wordBreak(string str, vector<string>& wordDict) {
        
        set<string> s(wordDict.begin(),wordDict.end());
        
        int n = str.size();
        bool dp[n][n];
        for(int gap=0;gap<n;gap++) {
            for(int i=0,j=gap;j<n;i++,j++) {
                
                if(gap==0) {
                    if(s.find(str.substr(i,j-i+1))!=s.end())
                        dp[i][j] = true;
                    else
                        dp[i][j] = false;
                }
                else
                {
                    if(s.find(str.substr(i,j-i+1))!=s.end())
                        dp[i][j] = true;
                    else
                    {
                        for(int k=i;k<j;k++) 
                        {
                            dp[i][j] = dp[i][k]&&dp[k+1][j];
                            if(dp[i][j])
                                break;
                        }
                    }
                }
            }
        }
        return dp[0][n-1];
        
    }
};
// Time Complexity : O(n^3),   Space Complexity : O(n^2)

Space Optimized DP (IB Accepted)

int breakRec(string A, vector<string> &dict, vector<int> &dp)
{
    int n = A.size();
    
    if(n == 0)
    {
        return 1;
    }
    
    if(dp[n] == -1)
    {
        dp[n] = 0;
        
        for(int i = 0; i<dict.size(); i++)
        {
            int len = dict[i].length();
            
            if(len > n)
            {
                continue;
            }
            
            if(dict[i] == A.substr(0,len) && breakRec(A.substr(len), dict, dp))
            {
                dp[n] = 1;
                return 1;
            }
        }
    }
    
    return dp[n];
}

int Solution::wordBreak(string A, vector<string> &B) {
    vector<int> dp(A.length() + 1, -1);
    
    return breakRec(A,B,dp);
}

Using Trie

class Solution {
public:
struct TrieNode { 
        char data;
        bool wordend;
       
        
        TrieNode *child[26];
        
        TrieNode (char ch)
        {
            data = ch;
            wordend = false;
           
            for(int i=0;i<26;i++)
            child[i] = NULL;
        }
    };
    
    TrieNode *root = new TrieNode('/');
    
    void insert(string str)
    {
        TrieNode *curr = root;
        
        for(int i=0;i<str.size();i++)
        {
            int index = str[i]-'a';
            if(!curr->child[index])
                curr->child[index] = new TrieNode(str[i]);
            
            
            curr = curr->child[index];
            
        }
        curr->wordend = true;
        
    }
    
    bool search(string str) 
    {
        TrieNode *curr = root;
        
        for(int i=0;i<str.size();i++)
        {
            int index = str[i]-'a';
            if(!curr->child[index])
                return false;
            
            
            curr = curr->child[index];
        }
        return curr->wordend;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        
        for(string word:wordDict)
            insert(word);
        
        return solve(s);
        
        
        
    }
    bool solve(string s)
    {
        int n = s.size();
        **if(!n)
            return true;**
        for(int i=1;i<=n;i++)
        {
            if(search(s.substr(0,i))&& solve(s.substr(i,n-i)))
                return true;
        }
        return false;
    }
};