跳至主要內容

0242. 有效的字母异位词

ITCharge大约 1 分钟

0242. 有效的字母异位词open in new window

  • 标签:哈希表、字符串、排序
  • 难度:简单

题目链接

题目大意

描述:给定两个字符串 sstt

要求:判断 ttss 是否使用了相同的字符构成(字符出现的种类和数目都相同)。

说明

  • 字母异位词:如果 sstt 中每个字符出现的次数都相同,则称 sstt 互为字母异位词。
  • 1s.length,t.length5×1041 \le s.length, t.length \le 5 \times 10^4
  • sstt 仅包含小写字母。

示例

  • 示例 1:
输入: s = "anagram", t = "nagaram"
输出: True
  • 示例 2:
输入: s = "rat", t = "car"
输出: False

解题思路

思路 1:哈希表

  1. 先判断字符串 sstt 的长度,不一样直接返回 False
  2. 分别遍历字符串 sstt。先遍历字符串 ss,用哈希表存储字符串 ss 中字符出现的频次;
  3. 再遍历字符串 tt,哈希表中减去对应字符的频次,出现频次小于 00 则输出 False
  4. 如果没出现频次小于 00,则输出 True

思路 1:代码

def isAnagram(self, s: str, t: str) -> bool:
    if len(s) != len(t):
        return False
    strDict = dict()
    for ch in s:
        if ch in strDict:
            strDict[ch] += 1
        else:
            strDict[ch] = 1
    for ch in t:
        if ch in strDict:
            strDict[ch] -= 1
            if strDict[ch] < 0:
                return False
        else:
            return False
    return True

思路 1:复杂度分析

  • 时间复杂度O(n+m)O(n + m),其中 nnmm 分别为字符串 sstt 的长度。
  • 空间复杂度O(S)O(|S|),其中 SS 为字符集大小,此处 S==26S == 26