Golang Solution


  • 0
    H
    // this is a dp solution
    func wordBreak(s string, wordDict []string) bool {
    	// put the words in map for fast lookup
    	wordMap := make(map[string]bool)
    	for _, e := range wordDict {
    		wordMap[e] = true
    	}
    
    	// state: f[i] means whether the substring [0:i] is breakable or not, note that i is inclusive
    	breakable := make([]bool, len(s) + 1)
    
    	// init: f[0] = true since s[0:0] is empty string which default to true
    	breakable[0] = true
    
    	// func: f[i] = f[j] == true && s[j : i] is in dict for j>= 0 && j <= i - 1
    	// note the state is inclusive, so f[j] means s[0:j] with j inclusive, so the rest of string is s[j:i] not s[j+1:i]
    	// j's range is from 0, to i - 1 because if j = i, s[j:i] becomes empty
    	for i := 1; i <= len(s); i++ {
    		for j := 0; j <= i-1; j++ {
    			sub := s[j:i]
    			if _, ok := wordMap[sub]; breakable[j] == true && ok {
    				breakable[i] = true
    				break
    			}
    		}
    	}
    
    	//answer
    	return breakable[len(s)]
    }
    

Log in to reply
 

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