- 当前位置：首页 >系统运维 >哈希表妙解字母异位词
哈希表妙解字母异位词
发布时间：2025-11-05 00:34:45 来源：创站工坊 作者：应用开发
本文转载自微信公众号「程序员小熊」，哈希作者程序员小熊。表妙转载本文请联系程序员小熊公众号。解字
前言
大家好，母异我是位词来自于华为的程序员小熊。今天给大家带来一道与哈希表相关的哈希题目，这道题同时也是表妙微软、字节、解字谷歌和亚马逊等互联网大厂的母异面试题，即力扣上第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] = ; 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 TrueGolang
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。云服务器提供商
IT资讯网源码库益华科技香港云服务器源码下载IT技术网企商汇服务器租用亿华云益强编程舍极客码头运维纵横益强IT技术网益强智未来益强科技亿华智慧云思维库多维IT资讯IT资讯网技术快报科技前瞻编程之道益强前沿资讯创站工坊亿华灵动汇智坊云智核亿华科技码力社益华IT技术论坛全栈开发益华科技亿华云计算亿华互联极客编程智能时代益强资讯优选亿华云益强数据堂亿华智造益强智囊团云站无忧益强编程堂
- Copyright © 2025 Powered by 哈希表妙解字母异位词,创站工坊 滇ICP备2023006006号-44sitemap