49. Group Anagrams

//: Playground - noun: a place where people can play

import UIKit

/*
 49. Group Anagrams
 Given an array of strings, group anagrams together.
 
 For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
 Return:
 
 [
 ["ate", "eat","tea"],
 ["nat","tan"],
 ["bat"]
 ]
 
 */
/*
 Thinking:
 //Error: 因为Set 是不能有相同元素的，如果aba，则只保留了ab，
 这样ab，和aba 就认为是一样了，如果再加上一个长度匹配来做，也是不行的，
 因为aba，abb 也被认为一样了。
 如果用Set 概念，把每一个元素都转换成一个Set ，然后最后的从头开始
 比较，相等则丢入第一个，Set 第一个比较完，跳到下一个，继续比较，
 直到SetArray 到结尾。
 
 //第二套方案：
 首先我们这样玩，由于是26个小写字母，我们把每个元素转换为26个数组堆
     a b c ... z
     2 0 1 ... 0 
 遍历字母，排好序，重新生成新的字符串，最后只要字符串相等，就认为是同一组素，（这里是不是可以再引申一下，我只需要，比较两个元素比较上是否相等，就认为是同一元素）
 
 //第三套方案：
 我们再利用Set 的特性，先把里面每个元素都有序
 比如aba -> aab, 然后把String 数组转换为Set,
 这样就变成了最后一共存在多少个数组，
 然后遍历Set，如果对应的内容相等，则丢进对应的Array中
 -----------------------------
  原始 [String]
     |
  每个元素自排序[OrderedString]  O(n)
     |
  Set<String>       Set内部时间复杂度
     |
  [[String]]         O(n*m)
 
 貌似空间复杂度有点高.
 
 */

func groupAnagrams(_ strs: [String]) -> [[String]] {
    guard strs.count > 0 else {
        return [[]]
    }
    
    
    //Error1: 这种方法太耗时, 实际上不就是把一个字符串转换为数组排序么
//    let aValue = ("a" as UnicodeScalar).value // 65
//    func orderString(_ str: String) -> String {
//        var charArray:[Int8] = Array<Int8>(repeating: 0, count: 26)
//        var maxDistance = 0
//        var minDistance = -1
//        for charValue in str.unicodeScalars {
//            let distance = Int(charValue.value - aValue)
//            charArray[distance] += 1
//            if (minDistance == -1) {
//                minDistance = distance
//            }
//            minDistance = distance < maxDistance ? distance : minDistance
//            maxDistance = distance > maxDistance ? distance : maxDistance
//        }
//        
//        let range = Range(maxDistance+1..<26)
//        charArray.removeSubrange(range)
//        if minDistance > 0 {
//            let range = Range(0..<minDistance)
//            charArray.removeSubrange(range)
//        }
//        let strArray = charArray.map{String($0)}
//        return strArray.joined()
//    }
//    
//    let orderedStrs = strs.map{orderString($0)}
    
    let orderedStrs = strs.map{String($0.characters.sorted())}
    print(orderedStrs)
 
    //Error2: 如果用set 的方法，来做，最后的算法复杂度在O(n*m),
    //实际上只需用一个字典(key, [String]), 如果之前已经包含了这个key，就合并，没有包含，就新增，最后把Value提升到二维返回即可
//    let setStrs = Set(orderedStrs)
//    var retArray: [[String]] = [[String]](repeatElement([], count: setStrs.count))
//    for (index, value) in setStrs.enumerated() {
//        for (i, v) in orderedStrs.enumerated() {
//            if (value == v) {
//                retArray[index].append(strs[i])
//            }
//        }
//    }
    
    var dict:[String: [String]] = [String: [String]]()
    for (i, v) in orderedStrs.enumerated() {
        if let _ = dict[v] {
            dict[v]!.append(strs[i])
        }
        else {
            dict[v] = [String]()
            dict[v]!.append(strs[i])
        }
    }
    
    let retArray: [[String]] = dict.values.map{Array<String>($0)}

    return retArray
}