[LeetCode]242. 有效的字母异位词(Valid Anagram)

题目描述

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

示例 1:

输入: s = “anagram”, t = “nagaram”
输出: true

示例 2:

输入: s = “rat”, t = “car”
输出: false

说明:
你可以假设字符串只包含小写字母。

解题思路

  • 排序。直接将两个字符串排序,然后比较是否相等。
  • 哈希表。构建一个哈希表,对一个字符串,加上其字母出现的次数,对第二个字符串,减去其字母出现的次数,最后查看哈希表的所有值是否为0。

代码

Python 3.6

排序

1
2
3
4
5
6
7
8
9
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
s_sort = sorted(s)
t_sort = sorted(t)
if s_sort == t_sort:
return True
return False

执行用时: 88 ms
内存消耗: 13.8 MB

哈希表

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
hashmap = {}
for i in range(len(s)):
hashmap[s[i]] = hashmap.setdefault(s[i], 0) + 1
hashmap[t[i]] = hashmap.setdefault(t[i], 0) - 1
for value in hashmap.values():
if value != 0:
return False
return True

执行用时: 88 ms
内存消耗: 13 MB