Golang 3ms solution


  • 0
    R
    import "strings"
    
    func wordBreak(s string, wordDict []string) []string {
        mp := make(map[string][]string)
        return dfs(s, wordDict, mp)    
    }
    
    func dfs(s string, wordDict []string, mp map[string][]string) []string {
        _, ok := mp[s]
        if ok {
            return mp[s]
        }
        
        res := make([]string, 0)
        if len(s) == 0 {
            res = append(res, "")
            return res
        }
        for _,word:= range wordDict {
            if strings.HasPrefix(s, word) {
                sublist := dfs(s[len(word):], wordDict, mp)
                for _, sub:= range sublist {
                    a := " "
                    if len(sub) == 0 {
                        a = ""
                    }
                    res = append(res, word + a + sub)
                }
            }        
        }
        mp[s] = res
        return res
    }
    

Log in to reply
 

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