題目：
Write a method anagram(s,t) to decide if two strings are anagrams or not.
Example
Given s="abcd", t="dcab", return true.
Challenge
O(n) time, O(1) extra space
題解1 - hashmap 統(tǒng)計字頻：
判斷兩個字符串是否互為變位詞坷随，若區(qū)分大小寫房铭，考慮空白字符時，直接來理解可以認為兩個字符串的擁有各不同字符的數(shù)量相同温眉。對于比較字符數(shù)量的問題常用的方法為遍歷兩個字符串缸匪，統(tǒng)計其中各字符出現(xiàn)的頻次，若不等則返回false. 有很多簡單字符串類面試題都是此題的變形題类溢。
class Solution {
public:
/**
* @param s: The first string
* @param b: The second string
* @return true or false
*/
bool anagram(string s, string t) { //空字符串凌蔬，錯誤
if (s.empty() || t.empty()) {
return false;
}
if (s.size() != t.size()) { //源字符串與目標字符串長度不同，錯誤
return false;
}
int letterCount[256] = {0}; //申請256字節(jié)的空間作為緩存區(qū)
for (int i = 0; i != s.size(); ++i) { //第一次遍歷闯冷，分別選取源字符和目標字符作為鍵
++letterCount[s[i]];
--letterCount[t[i]];
}
for (int i = 0; i != t.size(); ++i) { //第二次遍歷砂心，如果緩沖區(qū)中數(shù)據(jù)不為零，錯誤
if (letterCount[t[i]] != 0) {
return false;
}
}
源碼分析
兩個字符串長度不等時必不可能為變位詞(需要注意題目條件靈活處理)蛇耀。
初始化含有256個字符的計數(shù)器數(shù)組辩诞。
對字符串 s 自增，字符串 t 遞減纺涤，再次遍歷判斷l(xiāng)etterCount數(shù)組的值译暂，小于0時返回false.
在字符串長度較長(大于所有可能的字符數(shù))時抠忘，還可對第二個for循環(huán)做進一步優(yōu)化，即t.size() > 256時外永，使用256替代t.size(), 使用i替代t[i].（所有的字符只有256個）
return true;
}
};
題解2 - 排序字符串
另一直接的解法是對字符串先排序崎脉，若排序后的字符串內容相同，則其互為變位詞伯顶。題解1中使用 hashmap 的方法對于比較兩個字符串是否互為變位詞十分有效荧嵌，但是在比較多個字符串時，使用 hashmap 的方法復雜度則較高砾淌。
class Solution {
public:
/**
* @param s: The first string
* @param b: The second string
* @return true or false
*/
bool anagram(string s, string t) {
if (s.empty() || t.empty()) {
return false;
}
if (s.size() != t.size()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
if (s == t) {
return true;
} else {
return false;
}
}
};
