Javascript DP beats 91%; Golang DP 3ms


  • 0
    R

    Javascript:

    var wordBreak = function(s, wordDict) {
        if (!wordDict || wordDict.length == 0) return false
        var dp = new Array(s.length + 1);
        dp.fill(false)
        dp[0] = true
        
        for(var i = 1; i <= s.length; i++) {
            for(var j = 0; j < i; j++) {
                if(dp[j] && wordDict.indexOf(s.substring(j, i)) >= 0) {
                    
                    dp[i] = true
                    break;
                }
            }
        }
        return dp[s.length]
    };
    

    Golang:

    func wordBreak(s string, wordDict []string) bool {
        if wordDict == nil || len(wordDict) == 0 { return false }
        dp := make([]bool, len(s) + 1)
        for k, _:= range dp {
            dp[k] = false
        }
    
        dp[0] = true
        sort.Strings(wordDict)
    
        for i := 1; i <= len(s); i++ {
            for j := 0; j < i; j++ {
                if dp[j] && stringInSlice(s[j:i], wordDict) {
                    
                    dp[i] = true
                    break
                }
            }
        }
        return dp[len(s)]
    }
    
     func stringInSlice(str string, list []string) bool {
     	for _, v := range list {
     		if v == str {
     			return true
     		}
     	}
     	return false
     }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.