Golang concise solution using BFS


  • 0

    Build a tree in a BFS manner to check all concatenations of words among wordDict repeatedly.
    To avoid TLE and MLE,

    1. drop if a word does not match to a prefix of s (no possibility to match to s how many more words are prepended)
    2. don't proceed if we already add the same string to a tree (using map to manage this)
    func wordBreak(s string, wordDict []string) bool {
        dlen := len(wordDict)
        mp := make(map[string]bool) // caching
        
        var que []string
        word := ""
        for  {
            for i := 0; i < dlen; i++ {
                newWord := word + wordDict[i]
                if _, ok := mp[newWord]; ok {
                    continue
                }
                
                if newWord == s {
                    return true
                }
                if nlen := len(newWord); nlen >= len(s) || newWord != s[:nlen] {
                    continue
                }
                
                mp[newWord] = true
                que = append(que, newWord)
            }
            
            if len(que) == 0 {
                break
            }
            word = que[0]
            que = que[1:]
        }
        return false
    }
    
    

Log in to reply
 

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