Soyo

Day 6 of 30 days Leetcode challenge

Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:

[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

  • All inputs will be in lowercase.
  • The order of your output does not matter.

Solution

Count characters in each string and make a key for hashmap
Key looks like a1b2...z1 or array of Integer

Time complexity: O(nk + n) // k : length of string, n : number of strings

class Solution {
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var map = [String : [String]] ()
        var keys = strs.map { $0.anaKey() }
        
        for i in 0..<strs.count {
            
            let val = strs[i]
            let key = keys[i]
            
            if var list = map[key] {
                list.append(val)
                map[key] = list
            }else{
                map[key] = [val]
            }
        }
        
        return Array(map.values)
    }
    
}

extension String {
    func anaKey() -> String {
        var countTable = Array(repeating: 0, count: 26) // can use this array as result
        
        for c in self {
            let index = Int(c.asciiValue! - Character("a").asciiValue!)
            countTable[index] = countTable[index] + 1
        }
        
        var result = ""
        for i in 0..<countTable.count {
            if countTable[i] > 0 {
                result.append(Character(UnicodeScalar(97 + i)!))
                result.append("\(countTable[i])")
            }
        }
        return result
    }
}

Comments