Leetcode Word Break problem solution

YASH PAL,

In this Leetcode Word Break problem solution we have 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.

Leetcode Word Break problem solution

Problem solution in Python.

class Solution:
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        dp, truelist = [False] * len(s), []
        for i in range(len(s)):
            if s[:i+1] in wordDict:
                dp[i] = True
                truelist.append(i)
                continue
            for j in truelist:
                if s[j+1:i+1] in wordDict:
                    dp[i] = True
                    truelist.append(i)
                    break
        return dp[-1]

Problem solution in Java.

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        Set<Integer> set = new HashSet<Integer>();
        return dfs(s, 0, dict, set);
    }
    
    private boolean dfs(String s, int index, Set<String> dict, Set<Integer> set){
        if(index == s.length()) return true;
        if(set.contains(index)) return false;
        for(int i = index+1;i <= s.length();i++){
            String t = s.substring(index, i);
            if(dict.contains(t))
                if(dfs(s, i, dict, set))
                    return true;
                else
                    set.add(i);
        }
        set.add(index);
        return false;
    }
}

Problem solution in C++.

class Solution {
public:
    bool find(string s , int start , unordered_map<int,bool> &l1 , unordered_set<string> &l2){
        if(start>=s.length()) return true;
        if(l1.find(start)!=l1.end()) return l1[start];
        int l = s.length();
        string st = "";
        for(int i=start;i<l;i++){
            st+=s[i];
            if(l2.find(st)!=l2.end()){
                if(find(s,i+1,l1,l2)){
                    l1.insert(make_pair(i,true));
                    return true;
                }
            }
        }
        l1.insert(make_pair(start,false));
        return false;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_map<int,bool> l1;
        unordered_set<string> l2;
        for(string s:wordDict) l2.insert(s);
        return find(s,0,l1,l2);
    }
};

Problem solution in C.

bool compare (char *s, int i, char *d, int l, int len) {
    int n = 0;
    if (i+l > len)
        return false;
    while (n < l) {
        if (s[i+n] != d[n])
            return false;
        n++;
    }
    return true;
}

bool check (char * s, int len, char ** wordDict, int n) {
        
    int i,j, wlen;
    bool *mem = (bool*)calloc((len+20), sizeof(bool));
    bool res;
    mem[0] = true;
    
    for ( i = 0; i < len; i++) {
        if (mem[i] == false)
            continue;
        for (j = 0; j <= n; j++) {
            wlen = strlen(wordDict[j]);
            mem[i+ wlen] = mem[i+ wlen] || compare (s, i, wordDict[j], wlen, len);
        }
    }
    return mem[len];
}

bool wordBreak(char * s, char ** wordDict, int wordDictSize){

    return check (s, strlen(s), wordDict, wordDictSize-1);
    
}

coding problems