哈希表魔术解字母字谜

本文转载自微信公众号《程序员熊》，作者程序员熊。转载本文请联系程序员小熊公众号。前言大家好，我是华为程序员小熊。今天给大家带来一个哈希表相关的问题。这道题也是微软、字节跳动、谷歌、亚马逊等各大互联网公司的面试题，即扣题242-effectiveanagrams。本文主要介绍哈希表的策略来回答这个问题，供大家参考，希望对大家有所帮助。有效的变位词给定两个字符串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*104sandt只包含小写字母根据上面的变位词定义，两个字符串要互为变位词必须满足以下两个条件：长度相等；相同的字符出现相同的次数。对于任何与字母出现频率有关的问题，都可以考虑使用哈希表来解决。可以用字母作为哈希表的键，字母出现的次数作为哈希表的值。以判断s=”anagram”和t=”nagaram”是否互为anagram为例，如下图所示。例子定义一个数组（C语言用数组来模拟哈希表）或者哈希表（C++等语言），使用s[i]-'a'作为哈希表的key，使用s[i]以字符串s中出现的次数作为值；哈希表遍历字符串s和t，当遇到s中的字符时，将哈希表中记录的值加1，否则减1；对字符串s中字符的处理是根据字符对字符串t中的字符进行类推处理，使用哈希表策略的完整处理过程如下图所示：ThecompletehashtableprocessingprocessShowmeCodeCboolisAnagram(char*s,char*t){/*判断字符串是否为空，如果为空则不能用strlen求长度*/if(s==NULL&&t==NULL){returntrue;}elseif(s==NULL&&t!=NULL||s!=NULL&&t==NULL){returnfalse;/*两个非空字符串长度不同，不能互为变位词*/}elseif(strlen(s)!=strlen(t)){returnfalse;}/*数组模拟哈希表*/charhash[26]={0};for(inti=0;s[i]!='\0';++i){hash[s[i]-'a']++;hash[t[i]-'a']--;}for(inti=0;i<26;++i){if(hash[i]!=0){returnfalse;}}returntrue;}C++boolisAnagram(strings,stringt){if(s.length()!=t.length()){returnfalse;}intlen=s.length();unordered_maprecord;for(inti=0;ibool:iflen(s)！=len(t):returnFalsehash=[0]*26foriinrange(len(s)):hash[ord(s[i])-ord("a")]+=1foriinrange(len(t)):hash[ord(t[i])-ord("a")]-=1foriinrange(26):ifhash[i]!=0:returnFalsereturnTrueGolangfuncisAnagram(sstring,tstring)bool{iflen(s)!=len(t){returnfalse}varhash[26]intfori:=ranges{hash[s[i]-'a']++hash[t[i]-'a']--}for_,v:=rangehash{ifv!=0{returnfalse}}returntrue}复杂度分析时间复杂度：O(n)，其中n为字符串长度，需要遍历字符串空间复杂度：O(S)，其中S为字符集大小，S=26。