242.有效的字母异位词
一、问题描述
给定两个字符串 s 和 t，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1：
输入：s = "anagram", t = "nagaram"
输出：true示例 2：
输入：s = "rat", t = "car"
输出：false说明：你可以假设字符串只包含小写字母。
二、方案一：排序法
1、思路
将两个字符串分别排序，然后比较排序后的字符串是否相同。如果相同，则 t 是 s 的字母异位词。
2、代码实现
go
func isAnagram(s string, t string) bool {
return sortString(s) == sortString(t)
}
func sortString(s string) string {
sort.Strings([]string{s})
return s
}3、复杂度分析
- 时间复杂度：O(mlogm + nlogn)，其中 m 和 n 分别是两个字符串的长度。排序操作的时间复杂度为 O(mlogm) 和 O(nlogn)。
- 空间复杂度：O(m)，排序操作需要额外的空间。
三、方案二：哈希表法
1、思路
使用一个哈希表来统计 s 中每个字符的出现次数。然后遍历 t，减少相应字符的出现次数。如果在遍历过程中，某个字符的出现次数小于零或者在 s 中不存在该字符，则 t 不是 s 的字母异位词。
2、代码实现
go
func isAnagram(s string, t string) bool {
charCount := map[byte]int{}
// 统计s中每个字符的出现次数
for _, char := range s {
charCount[char]++
}
// 遍历t，减少相应字符的出现次数
for _, char := range t {
charCount[char]--
if charCount[char] < 0 {
return false
}
}
// 检查所有字符的出现次数是否为0
for _, count := range charCount {
if count != 0 {
return false
}
}
return true
}3、复杂度分析
- 时间复杂度：O(m + n)，其中 m 和 n 分别是两个字符串的长度。
- 空间复杂度：O(m)，需要存储
s中每个字符的出现次数。
四、总结
| 方案 | 时间复杂度 | 空间复杂度 | 备注 |
|---|---|---|---|
| 排序法 | O(mlogm + nlogn) | O(m) | 排序操作需要额外空间 |
| 哈希表法 | O(m + n) | O(m) | 直接在原字符串上操作 |
哈希表法在时间复杂度上优于排序法，因为它不需要额外的空间来存储排序后的字符串。在实际应用中，如果对空间复杂度有要求，通常更倾向于使用哈希表法。