LeetCode演算法題-Valid Anagram（Java實現）
這是悅樂書的第198 次更新，第205 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第61題（順位題號是242）。給定兩個字串s和t，寫一個函式來確定t是否是s的anagram。例如：
輸入：s =“anagram”，t =“nagaram”
輸出：true
輸入：s =“rat”，t =“car”
輸出：false
注意：您可以假設該字串僅包含小寫字母。
跟進：如果輸入包含unicode字元怎麼辦？ 您如何使您的解決方案適應這種情況？
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
關於題目中anagram的意思，結合給出的兩個示例，大意就是兩字串使用的小寫字母一樣，但是每個字母所處的位置不是全都一樣。此解法是將兩字串s、t轉換為字元陣列，然後將陣列排序，最後比較兩陣列的元素是否相等，這裡藉助了工具類Arrays。
此解法的時間複雜度是O(nlog(n))，空間複雜度是O(n)。
public boolean isAnagram(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
char[] ch = s.toCharArray();
char[] ch2 = t.toCharArray();
Arrays.sort(ch);
Arrays.sort(ch2);
return Arrays.equals(ch, ch2);
}
03 第二種解法
題目限制了只有英文小寫字母，我們可以定義一個長度只有26的整數陣列，對字串進行遍歷，以當前字元減去字元a所表示的整數為索引，找到對應元素，字串s所在的字元進行自增，字串t所在的字元進行自減，然後判斷陣列中的元素，只要任一元素不等於0，則說明s和t不滿足anagram的條件。
此解法時間複雜度是O(n)，空間複雜度是O(1)。
public boolean isAnagram2(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
int[] arr = new int[26];
for (int i=0; i<s.length(); i++) {
arr[s.charAt(i)-'a']++;
arr[t.charAt(i)-'a']--;
}
for(int num : arr) {
if (num != 0) {
return false;
}
}
return true;
}
04 第三種解法
使用HashMap，key為字串的單個字元，value為此字元出現的次數，這裡藉助HashMap的getOrDefault方法來實現，如果存在該key，返回對應的value，否則返回預設值。
先將字串s的每個字元存入HashMap中，然後遍歷字串字串t，依次獲取每一個字元，如果當前字元不在HashMap中存在，直接返回false，然後將字元存進HashMap中，value值減1，如果當前字元的出現次數為0了，將其remove掉，最後判斷HashMap是否為空。
此解法因為用到了map.containsKey()方法，所以時間複雜度最好的情況是O(n)，最壞的情況是O(n^2)，空間複雜度是O(n)。
public boolean isAnagram3(String s, String t) {
if (s == null || t == null || s.length() != t.length()) {
return false;
}
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for (int i=0; i<s.length(); i++) {
char ch = s.charAt(i);
map.put(ch, map.getOrDefault(ch, 0)+1);
}
for (int j=0; j<t.length(); j++) {
char ch = t.charAt(j);
if (!map.containsKey(ch)) {
return false;
}
map.put(ch, map.get(ch)-1);
if (map.get(ch) == 0) {
map.remove(ch);
}
}
return map.isEmpty();
}
此解法是可以應對那些帶有unicode字元的字串，當然也可以使用像第二種解法的那樣，使用陣列，但是陣列容量要擴大到256，其他的思路都是一樣的。
05 小結
演算法專題目前已連續日更超過一個月，演算法題文章61 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！