Golang concise solution beats 95% other solutions


  • 0

    Create an alphabet character appearance count table for each strings.
    A table looks like "00000000000000000000000000" and holds a number of character from a to z.
    For example, a table for cabzz looks like 11100000000000000000000002.

    After creating these tables, compare each table (tables are string format, so I can compare just by = operator, no need for an iteration) by using map.

    Let's say strs = ["abc", "acb", "abb", "bac"].
    Tables are ["1110...", "1110...", "120...", "1110..."]
    Starts from index 0 of tables, since this is the first trial, set map["1110..."] = 0, then add strs[0] to anagramGroup as a new index. Next index (1) a table is 1110..., and map[1110...] exists and value is 0, so put strs[1] to anagramGroup[0]. Next 2 th index, a table is 120... and this doesn't exist in a map, so we need to add strs[2] again as a new index (this time, 1). So we need to memorize the latest new index (newIndex in a code below).

    mapIndex which is a value of mp represents which index among anagram groups we should add if the anagram group already exists.

    func groupAnagrams(strs []string) [][]string {
    	alphaBits := make([]string, len(strs))
    	for i, str := range strs {
    		alphaBits[i] = getAlphabetBit(str)
    	}
    
    	var res [][]string
    	newIndex := 0
    	mp := make(map[string]int)
    	for bitIndex, alphaBit := range alphaBits {
    		if mapIndex, ok := mp[alphaBit]; !ok {
    			mp[alphaBit] = newIndex
    			res = append(res, []string{strs[bitIndex]})
    			newIndex++
    			continue
    		} else {
    			res[mapIndex] = append(res[mapIndex], strs[bitIndex])
    		}
    	}
    	return res
    }
    
    func getAlphabetBit(str string) string {
    	res := make([]int, 26)
    	for _, ch := range str {
    		chInt := int(ch - 'a')
    		res[chInt] += 1
    	}
    
    	var b bytes.Buffer
    	for _, bit := range res {
    		b.WriteByte(byte(int('0') + bit))
    	}
    	return b.String()
    }
    
    
    

Log in to reply
 

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