14 | 面试题：有效的字母异位词

题目：

242. 有效的字母异位词

解法一：排序

两组词汇按词典序排序后进行对比，一样则为字母异位词，无序的排序优先使用快排，时间复杂度：O(N*logN)

解法二：计数，所有和计数相关的首先考虑 MAP（优解）

即判断两组词汇中字母的出现个数，使用MAP进行计数 {字母:次数}

时间复杂度：数个数需要遍历，则为O(N) 每次进行MAP的操作为O(1) 所以最终为：O(N*1) = O(N)

class Solution {
    fun isAnagram(s: String, t: String): Boolean {
        var m1 = mutableMapOf<Char,Int>()
        var m2 = mutableMapOf<Char,Int>()

        s.toCharArray().forEach{
            var value=m1[it]?:0
            m1[it] = ++value
        }

        t.toCharArray().forEach{
            var value=m2[it]?:0
            m2[it] = ++value
        }
        return m1==m2
    }
}

解法二点一：计数的不同写法

对于该题，由于有个特点，仅为小写字母，始终只有26个字母，则可以这样做：使用两个数组代替解法二的两个MAP，使用两组词汇字母的ASIC码值- ‘a’ 的ASIC码值来确定数组下标，将下标对应位置的值+1即可。

实际上这就是解法二的思想，只是自行实现了大小为26，哈希函数为【字母的ASIC码值- ‘a’ ASIC码值】的哈希表。

时间复杂度： O(N)

Python 版本的解法二三对比：