算法练习第七天——有效的字母异位词

算法练习第七天——有效的字母异位词

有效的字母异位词题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例一：

输入: s = "rat", t = "car" 输出: false

示例二：

输入: s = "abcd", t = "daeb" 输出: false

示例三：

输入: s = "coio", t = "ooci" 输出: true

解题思路

方法一：哈希表

t 是 s 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含 26 个小写字母，因此我们可以维护一个长度为 26 的频次数组 table，先遍历记录字符串 s 中字符出现的频次，然后遍历字符串tt，减去 table 中对应的频次，如果出现 table[i]<0，则说明 t 包含一个不在 s 中的额外字符，返回 false 即可

以下代码以golang为例子：

func isAnagram(s, t string) bool {
    var c1, c2 [26]int
    for _, ch := range s {
        c1[ch-'a']++
    }
    for _, ch := range t {
        c2[ch-'a']++
    }
    return c1 == c2
}

也可以只创建一张哈希表然后先对第一个字符串进行填写，第二个字符串去消对应value，再消value前要进行匹配如果该字母(key)存在value--，否则直接返回false，等第二个字符串遍历完后观察表中所有value是否都为0，都为0返回true，反之返回false

该解法复杂度分析

• 时间复杂度：O(n)，其中 n 为 s 的长度。

• 空间复杂度：O(S)，其中 S 为字符集大小，此处 S=26。
• 
  

方法二：排序

s和t中元素相同只是位置不同，因此我们可以对两个字符串进行排序，讲字符转化为byte类型进行从小到大的排序，最后将两字符串进行对比即可。

func isAnagram(s, t string) bool {
    s1, s2 := []byte(s), []byte(t)
    sort.Slice(s1, func(i, j int) bool { return s1[i] < s1[j] })
    sort.Slice(s2, func(i, j int) bool { return s2[i] < s2[j] })
    return string(s1) == string(s2)
}

该解法复杂度分析

• 时间复杂度：O(nlogn)，其中 n 为 s 的长度。

• 空间复杂度：O(logn)。