判斷兩個字符串中的字母是否一致

大家好，我是吳師兄

今天的題目來源于 LeetCode 第 242 號問題：有效的字母異位詞，難度為「簡單」。

一、題目描述

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

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

示例 1:

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

示例 2:

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

提示:

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

進階:如果輸入字符串包含 unicode 字符怎么辦？你能否調(diào)整你的解法來應對這種情況？

二、題目解析

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

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

沒錯，就是哈希表！

解法思路很簡單。

1、首先先判斷兩個字符串長度是否相同，不相同直接返回false

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

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

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

三、參考代碼

1、Java 代碼

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

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

//直接返回false
returnfalse;

}

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

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

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

}

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

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

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

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

}

}

//否則，說明是字母異位詞
returntrue;

}
}

2、C++ 代碼

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

//直接返回false
returnfalse;

}

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

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

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

}

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

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

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

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

}

}

//否則，說明是字母異位詞
returntrue;
}
};

3、Python 代碼

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

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

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

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

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

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


foriint:

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

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

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

#那就不是字母異位詞
returnFalse


#否則，說明是字母異位詞
returnTrue

四、復雜度分析

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

審核編輯 ：李倩