哈希表妙解字母异位词
大家好，我是来自于华为的程序员小熊。今天给大家带来一道与哈希表相关的题目，这道题同时也是微软、字节、谷歌和亚马逊等互联网大厂的面试题，即力扣上第242题-有效的字母异位词。
本文主要介绍哈希表的策略来解答此题，供大家参考，希望对大家有所帮助。
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1：
输入: s = "anagram", t = "nagaram"
输出: true
示例 2：
输入: s = "rat", t = "car"
输出: false
提示：
1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母
解题思路
❝字母异位词：由相同的字母按照不同的顺序组成的单词。 ❞
根据上述字母异位词的定义可知，两个字符串要互为字母异位词，则必须满足一下两个条件：
- 长度相等；
- 相同字符出现的次数相同。
凡是涉及到字母出现的频次的相关问题，都可以考虑用哈希表去求解，可以以字母为哈希表的key，字母出现的次数作为哈希表的value。
举例
以判断 s = "anagram" 和 t = "nagaram" 是否互为字母异位词为例子，如下图示。
例子
定义一个数组（C 语言用数组模拟哈希表）或哈希表（C++ 等语言），以 s[i] - 'a' 作为哈希表的 key，以 s[i] 在字符串 s 中出现的次数作为 value；
哈希表
遍历字符串 s 和 t，遇到 s 中的字符时，对哈希表中记录的 value 加 1，否则减 1；
对字符串 s 中的字符的处理
对字符串 t 中的字符的处理
以此类推，采用哈希表的策略的完整处理过程，如下动图示：
哈希表处理完整过程
Show me the Code
C
bool isAnagram(char * s, char * t){
/* 判断字符串是否为空，为空则不能用 strlen 求长度 */
if (s == NULL && t == NULL) {
return true;
} else if (s == NULL && t != NULL || s != NULL && t == NULL) {
return false;
/* 两个非空字符串长度不等，肯定不互为字母异位词 */
} else if (strlen(s) != strlen(t)){
return false;
}
/* 数组模拟哈希表 */
char hash[26] = {0};
for (int i = 0; s[i] != '\0'; ++i) {
hash[s[i] - 'a']++;
hash[t[i] - 'a']--;
}
for (int i = 0; i < 26; ++i) {
if (hash[i] != 0) {
return false;
}
}
return true;
}
C++
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
int len = s.length();
unordered_map<int, int> record;
for (int i = 0; i < len; ++i) {
record[s[i] - 'a']++;
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; ++i) {
if (record[i] != 0) {
return false;
}
}
return true;
}
Java
boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] hash = new int[26];
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i) - 'a']++;
hash[t.charAt(i) - 'a']--;
}
for (int i : hash) {
if (i != 0) {
return false;
}
}
return true;
}
Python3
def isAnagram(self, s: str, t: str) -> bool:
if len(s) != len(t):
return False
hash = [0]*26
for i in range(len(s)):
hash[ord(s[i]) - ord("a")] += 1
for i in range(len(t)):
hash[ord(t[i]) - ord("a")] -= 1
for i in range(26):
if hash[i] != 0:
return False
return True
Golang
func isAnagram(s string, t string) bool {
if len(s) != len(t) {
return false
}
var hash [26]int
for i := range s {
hash[s[i] - 'a']++
hash[t[i] - 'a']--
}
for _, v := range hash {
if v != 0 {
return false
}
}
return true
}
复杂度分析
时间复杂度：O(n)，其中 n 是字符串的长度，需要遍历一遍字符串。
空间复杂度：O(S)，其中 S 为字符集大小，S = 26。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-07-26，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录