Golang solution using DFS with visited cache


  • 0

    This is accepted.
    By storing "already checked prefix" and discarding substring immediately if it doesn't match, it didn't get TLE.

    func wordBreak(s string, wordDict []string) bool {
        var res bool
        checked := make(map[string]bool)
        helper("", s, wordDict, &res, checked)
        return res
    }
    
    func helper(cur string, target string, wordDict []string, res *bool, checked map[string]bool) {
        if *res || len(cur) > len(target) || target[:len(cur)] != cur {
            return
        }
        
        if cur == target {
            *res = true
            return
        }
        
        if _, ok := checked[cur]; ok {
            return
        }
        
        checked[cur] = true
        for i := 0; i < len(wordDict); i++ {
            helper(cur + wordDict[i], target, wordDict, res, checked)
            if *res {
                return
            }
        }
    }
    

Log in to reply
 

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