Anagrams:是顛倒字母順序的字符串
本文提供三個方法，分別分析時間空間復雜度
方法一：暴力遍歷 時間復雜度：O(n^2)
方法二：基於排序算法，Sorting的時間復雜度是O(n*log(n))。所以先把兩個字符數字進行排序，再判斷。
public class CustomStringUtil
{
boolean firstIsAnagram(String sFirst, String sSecond)
{
char[] cFirstArray = sFirst.toCharArray();
char[] cSecondArray = sFirst.toCharArray();
Arrays.sort(cFirstArray);
Arrays.sort(cSecondArray);
return Arrays.equals(cFirstArray, cSecondArray);
}
}
分析：
（1）把一個String轉換成char[]，時間：O(n)，空間：O(n)（數組占用的）
（2）給數組排序：時間：O(n*log(n))，空間：O(n)
（2）比較這兩個數組：時間：O(n)，空間：O(1)（可能一些臨時計數器可能會用到一點空間）
總結：這個算法的時間復雜度是：O(n*log(n))
方法三：應用哈希表的思想。
首先我們知道，在ASCII Table中每個字符串對應一個整形數，這裡我們就利用這一點，把這個整形數當做數組的下標，這樣一個字符就對應到數組中的唯一一個位置。
算法思想：我們可以用一個數組，數組下標就是字符的索引，然後計算字符串中每個字符出現的次數。在第一個字符串中，每出現一個字符就在相應的數組位置上加一；在第二個字符串中，每出現一個字符就在數組相應的位置上減一。我們這樣操作先遍歷第一個字符串，再遍歷第二個字符串，這兩個字符串是Anagrams的唯一一種情況就是最後這個數組還是全0。就意味著這兩個字符串中某一個特定的字符個數相同。
算法步驟：
（1）生成一個236位的整數數組k
（2）對於第一個字符串sFirst中的每一個字符x，x對應的整型值是y，把k[y]加1
（3）對於第二個字符串sSecond中的每一個字符x，x對應的整型值是y，把k[y]減1
（4）如果數組k仍然是全零，那麼字符串sFirst和sSecond就是Anagrams
代碼：
public class CustomStringUtil
{
public static boolean secondIsAnagram(String sFirst, String sSecond)
{
if (sFirst.length() != sSecond.length())
{
return false;
}
int[] asciiChars = new int[256];
for (int i = sFirst.length() - 1; i>=0; --i)
{
++asciiChars[sFirst.charAt(i)]; //關鍵代碼
}
for (int i = sFirst.length() - 1; i>=0; --i)
{
char currChar = sSecond.charAt(i);
if (asciiChars[currChar] == 0)
{
return false;
}
--asciiChars[currChar];
}
return true;
}
}
分析：時間：O(n)（遍歷一次數組的時間）空間O(1)（空間不隨著處理的字符串的大小而變化）
注意：這上面的代碼做了一個假設：就是我們有一個確定的256個字符的集合。要注意到，這個假設對於編程來說是一個巨大的陷阱，我們應該非常小心。