算法练习第七天——有效的字母异位词
算法练习第七天——有效的字母异位词
有效的字母异位词题目
给定两个字符串 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)。