題目
這是一道微軟的面試題，題目是這樣的：兩個單詞如果包含相同的字母，次序不同，則稱為字母易位詞(anagram)。例如，“silent”和“listen”是字母易位詞，而“apple”和“aplee”不是易位詞。請定義函數檢查兩個單詞是否是字母易位詞。可以假設兩個單詞字母均為小寫。要求算法復雜度盡量低。
看到這個題目，你的第一想法是怎么做？
思路一
首先，最基本的思路，便是檢測字符串s1中的字符是否都出現在s2中（在s1和s2長度一樣的前提下）。為了解決“apple”和“aplee”不是易位詞的這種情況，不能僅僅判斷出現在s2中就可以了，還需要做個標記。將s2中已經和s1對應上的位置標記為0，C++實現如下：

bool anagramSolution1(string s1,string s2) {if(s1.size()!=s2.size())return false;bool stillOk=true;for(int i=0;i<s1.size()&&stillOk;i++){bool found=false;for(int j=0;j<s2.size()&&!found;j++){if(s2[j]==s1[i]){s2[j]=0;found=true;}}if(found){stillOk=true;}else{stillOk=false;}}return stillOk; }

讓我們考慮一下算法復雜度，對于s2中的每個元素，s1都會從頭開始遍歷一遍，所以算法的復雜度為O(n^2)。
可以想一想，有沒有算法復雜度比這個更低的呢？
思路二
通過題目，我們可以想到，字母易位詞即為各個字母的數目相同，而順序不一致。因而，如果對字符串按照字母順序排序后，那么兩個字符串應該完全一致。這樣算法復雜度是否更低？
C++實現如下：

bool anagramSolution2(string s1,string s2) {if(s1.size()!=s2.size())return false;sort(s1.begin(),s1.end());sort(s2.begin(),s2.end());return s1==s2; }

這個復雜度是多少呢，因為其中用到了排序算法（頭文件包含algorithm）和s1、s2比較的算法。所以復雜度為O(n*logn)。比思路一的復雜度降低了。
思路三
思路二利用了字母易位詞即為各個字母的數目相同，而順序不一致。我們從另外一個角度思考，字母一共有多少個？很明顯，只有26個（只考慮小寫字母）。那么，我們可以為字符串s1和s2分別設置26個計數器，然后判斷這對應位置的計數是否相等，如果對應計數完全相等，則為字母易位詞。
C++實現如下：

bool anagramSolution3(string s1,string s2) {if(s1.size()!=s2.size())return false;int count1[26]={0};int count2[26]={0};for(int i=0;i<s1.size();i++){count1[s1[i]-'a']+=1;}for(int j=0;j<s2.size();j++){count2[s2[j]-'a']+=1;}bool match=true;for(int idx=0;idx<26&&match;idx++){if(count1[idx]!=count2[idx]){match=false;}}return match; }

算法的復雜度為O（n+n+26），即為O（n），為線性復雜度的算法。

總結

以上是生活随笔為你收集整理的字母异位词（anagram）的不同复杂度实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。