大家好，我是吳師兄

今天的題目來(lái)源于 LeetCode 第 242 號(hào)問(wèn)題：有效的字母異位詞，難度為「簡(jiǎn)單」。

一、題目描述

給定兩個(gè)字符串s和t，編寫(xiě)一個(gè)函數(shù)來(lái)判斷t是否是s的字母異位詞。

注意：若s和t中每個(gè)字符出現(xiàn)的次數(shù)都相同，則稱(chēng)s和t互為字母異位詞。

示例 1:

輸入:s="anagram",t="nagaram"
輸出:true

示例 2:

輸入:s="rat",t="car"
輸出:false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s和t僅包含小寫(xiě)字母

進(jìn)階:如果輸入字符串包含 unicode 字符怎么辦？你能否調(diào)整你的解法來(lái)應(yīng)對(duì)這種情況？

二、題目解析

題目講的是讓你判斷兩個(gè)字符串中的字母是否一致，比如示例1中，s包含字母a、n、g、r、m，而t中也包含a、n、g、r、m，都是只有這五個(gè)字母，并且頻次相同，只是順序不同。

看到頻次這個(gè)詞，你腦海中第一想法是什么？

沒(méi)錯(cuò)，就是哈希表！

解法思路很簡(jiǎn)單。

1、首先先判斷兩個(gè)字符串長(zhǎng)度是否相同，不相同直接返回false

2、然后把s中所有的字符出現(xiàn)個(gè)數(shù)使用計(jì)數(shù)器統(tǒng)計(jì)起來(lái)，存入一個(gè)大小為 26 的數(shù)組中（注意題目的說(shuō)明）

3、最后再來(lái)統(tǒng)計(jì)t字符串，即遍歷t時(shí)將對(duì)應(yīng)的字母頻次進(jìn)行減少，如果期間 計(jì)數(shù)器出現(xiàn)小于零的情況，則說(shuō)明t中包含一個(gè)不存在于s中的字母，直接返回false。

4、最后檢查計(jì)數(shù)器是否歸零。

三、參考代碼

1、Java 代碼

//登錄AlgoMooc官網(wǎng)獲取更多算法圖解
//https://www.algomooc.com
//作者：程序員吳師兄
//代碼有看不懂的地方一定要私聊咨詢(xún)吳師兄呀
//有效的字母異位詞（LeetCode 242）：https://leetcode.cn/problems/valid-anagram/
classSolution{
publicbooleanisAnagram(Strings,Stringt){

//如果兩個(gè)字符串的長(zhǎng)度都不一致，那么肯定是無(wú)法成為字母異位詞的
if(s.length()!=t.length()){

//直接返回false
returnfalse;

}

//讓a-z這26個(gè)字母對(duì)應(yīng)的下標(biāo)變成0-25方便存到數(shù)組中
//比如a對(duì)應(yīng)的索引就是0
//b對(duì)應(yīng)的索引就是1
int[]table=newint[26];

//從頭到尾遍歷字符串s
for(inti=0;i//把訪問(wèn)的字符轉(zhuǎn)換為整數(shù)的形式
//比如訪問(wèn)字母a，那么-'a'之后就是0，就是a對(duì)應(yīng)的索引為0
intindex=s.charAt(i)-'a';

//那么意味著這個(gè)字母出現(xiàn)的頻次需要加1
table[index]++;

}

for(inti=0;i//把訪問(wèn)的字符轉(zhuǎn)換為整數(shù)的形式
//比如訪問(wèn)字母a，那么-'a'之后就是0，就是a對(duì)應(yīng)的索引為0
intindex=t.charAt(i)-'a';

//那么意味著這個(gè)字母出現(xiàn)的頻次需要減1
table[index]--;

//如果說(shuō)發(fā)現(xiàn)這個(gè)字母出現(xiàn)的頻次小于了0
//說(shuō)明t中出現(xiàn)了s中不曾用的字母
if(table[index]0){

//那就不是字母異位詞
returnfalse;

}

}

//否則，說(shuō)明是字母異位詞
returntrue;

}
}

2、C++ 代碼

classSolution{
public:
boolisAnagram(strings,stringt){
//如果兩個(gè)字符串的長(zhǎng)度都不一致，那么肯定是無(wú)法成為字母異位詞的
if(s.length()!=t.length()){

//直接返回false
returnfalse;

}

//讓a-z這26個(gè)字母對(duì)應(yīng)的下標(biāo)變成0-25方便存到數(shù)組中
//比如a對(duì)應(yīng)的索引就是0
//b對(duì)應(yīng)的索引就是1
vector<int>table(26,0);

//從頭到尾遍歷字符串s
for(inti=0;i//把訪問(wèn)的字符轉(zhuǎn)換為整數(shù)的形式
//比如訪問(wèn)字母a，那么-'a'之后就是0，就是a對(duì)應(yīng)的索引為0
intindex=s[i]-'a';

//那么意味著這個(gè)字母出現(xiàn)的頻次需要加1
table[index]++;

}

for(inti=0;i//把訪問(wèn)的字符轉(zhuǎn)換為整數(shù)的形式
//比如訪問(wèn)字母a，那么-'a'之后就是0，就是a對(duì)應(yīng)的索引為0
intindex=t[i]-'a';

//那么意味著這個(gè)字母出現(xiàn)的頻次需要減1
table[index]--;

//如果說(shuō)發(fā)現(xiàn)這個(gè)字母出現(xiàn)的頻次小于了0
//說(shuō)明t中出現(xiàn)了s中不曾用的字母
if(table[index]0){

//那就不是字母異位詞
returnfalse;

}

}

//否則，說(shuō)明是字母異位詞
returntrue;
}
};

3、Python 代碼

classSolution:
defisAnagram(self,s:str,t:str)->bool:

#如果兩個(gè)字符串的長(zhǎng)度都不一致，那么肯定是無(wú)法成為字母異位詞的
iflen(s)!=len(t):
#直接返回False
returnFalse

#讓a-z這26個(gè)字母對(duì)應(yīng)的下標(biāo)變成0-25方便存到數(shù)組中
#比如a對(duì)應(yīng)的索引就是0
#b對(duì)應(yīng)的索引就是1
table=[0]*26

#從頭到尾遍歷字符串s
foriins:

#把訪問(wèn)的字符轉(zhuǎn)換為整數(shù)的形式
#比如訪問(wèn)字母a，那么-'a'之后就是0，就是a對(duì)應(yīng)的索引為0
index=ord(i)-ord('a')

#那么意味著這個(gè)字母出現(xiàn)的頻次需要加1
table[index]+=1


foriint:

#把訪問(wèn)的字符轉(zhuǎn)換為整數(shù)的形式
#比如訪問(wèn)字母a，那么-'a'之后就是0，就是a對(duì)應(yīng)的索引為0
index=ord(i)-ord('a')

#那么意味著這個(gè)字母出現(xiàn)的頻次需要減1
table[index]-=1

#如果說(shuō)發(fā)現(xiàn)這個(gè)字母出現(xiàn)的頻次小于了0
#說(shuō)明t中出現(xiàn)了s中不曾用的字母
iftable[index]0:

#那就不是字母異位詞
returnFalse


#否則，說(shuō)明是字母異位詞
returnTrue

四、復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n)，其中 n 為 s 的長(zhǎng)度。
• 空間復(fù)雜度：O(S))，其中 S 為字符集大小，此處 S = 26 。

審核編輯 ：李倩