Golang and Javascript map solutions with explanation


  • 0
    R

    Here we put every word into a hashmap with value of 1. Then, we loop through the input array and delete the word from the hashmap. Next, we loop through each character of the word to see if we find a substring inside the hashmap keys. If we do, we just run a recursive into the next letter forward. If we get more than 2 substrings, then we add the word into the result array to return.

    func findAllConcatenatedWordsInADict(words []string) []string {
        res:= []string{}
        mp:= make(map[string]int)
        
        for _, word := range words {
            mp[word] = 1
        }
        
        for _, word := range words {
            delete(mp, word)
            
            c:=breakWord(word, mp)
            
            if c >1 {
                res = append(res, word)
            } else if c == 0 {
                mp[word] = 1
            }
        }
        return res
    }        
    
    func breakWord(word string, mp map[string]int) int {
        if _, ok := mp[word]; ok {
            return mp[word]
        }
        for i:=1; i < len(word); i++ {
            str:= word[0:i]
            _, ok := mp[str]
            if ok && mp[str] > 0 {
                c1 := mp[str]
                c2 := breakWord(word[i:], mp)
                
                if c2 > 0 {
                    mp[word] = c1 + c2
                    return c1 + c2
                }
            }
        }   
        mp[word] = 0
        return 0
    }
    

  • 0
    R

    Javascript version:

    var findAllConcatenatedWordsInADict = function(words) {
        res = []
        mp = {}
        words.forEach(function(word) {
            mp[word] = 1
        })
        
        words.forEach(function(word) {
            delete mp[word]
            
            var c = breakWord(word, mp)
            
            if(c>1) {
                res.push(word)
            } else if (c== 0) {
                mp[word] = 1
            }
        })
        return res
    };
    
    var breakWord = function(word, mp) {
        if(word in mp) return mp[word]
        for(var i = 1; i < word.length; i++) {
            var str = word.substring(0, i)
            if (str in mp && mp[str] > 0) {
                var c1 = mp[str]
                var c2 = breakWord(word.substring(i), mp)
                
                if(c2 > 0) {
                    mp[word] = c1 + c2
                    return c1 + c2
                }
            }
        }
        mp[word] = 0
        return 0
    }
    

Log in to reply
 

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