hash table hard

题目

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

  • 示例 1: ``` 输入: s = “anagram”, t = “nagaram” 输出: true

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

  1. > 你可以假设字符串只包含小写字母。
  3. <a name="QcKua"></a>
  4. # 思路
  6. 1. 首先判断两个字符串长度是否相等，不相等则直接返回 `false` 
  7. 1. 若相等，则初始化 `26`  个字母哈希表，遍历字符串 `s`  和 `t` 
  8. 1. `s`  负责在对应位置增加， `t`  负责在对应位置减少
  9. 1. 如果最后哈希表的值都为 0，则二者是字母异位词
  11. 复杂度分析分析：
  13. - 时间复杂度： `O(n)` 。因为访问计数器表是一个固定的时间操作。
  14. - 空间复杂度： `O(1)` 。尽管我们使用了额外的空间，但是空间的复杂性是 `O(1)` ，因为无论 `N`  有多大，表的大小都保持不变。
  15. [![Video_2020-07-16_155853.wmv (177.67KB)](https://gw.alipayobjects.com/mdn/prod_resou/afts/img/A*NNs6TKOR3isAAAAAAAAAAABkARQnAQ)](https://www.yuque.com/darrenzhang/wvzo6v/ialakl?_lake_card=%7B%22status%22%3A%22done%22%2C%22name%22%3A%22Video_2020-07-16_155853.wmv%22%2C%22size%22%3A181929%2C%22percent%22%3A100%2C%22taskId%22%3A%22XghiszZufjOd%22%2C%22margin%22%3Atrue%2C%22id%22%3A%22vGiYb%22%2C%22videoId%22%3A%22inputs%2Fprod%2Fyuque%2F2020%2F353587%2Fwmv%2F1594886359175-f3953a89-f2d8-4504-a157-1e7bf3258669.wmv%22%2C%22card%22%3A%22video%22%7D#vGiYb)<a name="3lD24"></a>
  16. # 代码实现
  17. ```python
  18. class Solution:
  19.     def isAnagram(self, s: str, t: str) -> bool:
  20.         if (len(s) != len(t)):
  21.             return False
  22.         hash_dict = {}
  23.         for item in s:
  24.             hash_dict[item] = hash_dict.get(item, 0) + 1
  25.         for item in t:
  26.             hash_dict[item] = hash_dict.get(item, 0) - 1
  28.         for i in hash_dict:
  29.             if hash_dict[i] != 0:
  30.                 return False
  31.         return True

补充

对于字典(Dictionary) get()函数 返回指定键的值，如果值不在字典中返回默认值。

  • 语法

    dict.get(key, default=None)

  • 参数

    • key — 字典中要查找的键。
    • default — 如果指定键的值不存在时，返回该默认值。
  • 返回值
    - 返回指定键 `key` 的值，如果值不在字典中返回默认值 `None` 。

本题还可以暴力求解：直接排序之后进行比较

return sorted(s) == sorted(t)

题解来源于