抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

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 版本的解法二三对比:


0条评论

发表评论