LeetCode_排序_中等_242.有效的字母異位詞

目錄

• 1.題目
• 2.思路
• 3.代碼實作（Java）

1.題目

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

注意：若 s 和 t 中每個字元出現的次數都相同，則稱 s 和 t 互為字母異位詞。

示例 1:

輸入: s = “anagram”, t = “nagaram”

輸出: true

示例 2:

輸入: s = “rat”, t = “car”

輸出: false

提示:

1 <= s.length, t.length <= 5 * 104

s 和 t 僅包含小寫字母

進階: 如果輸入字元串包含 unicode 字元怎麼辦？你能否調整你的解法來應對這種情況？

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/valid-anagram

2.思路

（1）排序

（1.1）先判斷字元串s和t的長度是否相等，若不相等則直接傳回false，否則繼續下一步；

（1.2）使用toCharArray()方法将字元串s和t分别轉換為其對應的字元數組schars和tchars；

（1.3）使用sort()方法對字元數組進行排序，然後再将它們轉換為字元串；

（1.4）最後傳回equals()方法比較的結果即可。

（2）哈希表

（2.1）先判斷字元串s和t的長度是否相等，若不相等則直接傳回false，否則繼續下一步；

（2.2）定義長度為26的數組map，用來存儲字元串s中的各個字元的個數，下标0對應字元a，下标1對應字元b…，依此類推；

（2.3）先周遊字元串s，将其所包含的字元個數情況儲存到數組map中。然後再周遊字元串t，每掃描到一個字元就先将map中該字元的個數減一，然後再判斷該字元的個數是否小于0，若小于0，則說明t不是s的字母異位詞，直接傳回false，否則繼續周遊；

（2.4）若在周遊字元串t的過程中沒有直接傳回false，則說明t是s的字母異位詞，最後傳回true即可。

3.代碼實作（Java）

//（1）排序
public boolean isAnagram(String s, String t) {
    if(s.length()!=t.length()){
        return false;
    }
    //把字元串轉化成字元數組
    char[] schars=s.toCharArray();
    char[] tchars=t.toCharArray();
    //對字元數組進行排序
    Arrays.sort(schars);
    Arrays.sort(tchars);
    //把字元數組轉換為字元串
    String sorteds=new String(schars);
    String sortedt=new String(tchars);
    return sorteds.equals(sortedt);
}
           

//（2）哈希表
public boolean isAnagram(String s, String t) {
    int sLen=s.length();
    int tLen=t.length();
    if (sLen!=tLen) {
        return false;
    }
    //0:a  1:b  2:c...  依此類推
    //map[i]=j:s中i對應的字元的個數為j
    int[] map = new int[26];
    for(int i=0;i<sLen; i++) {
        map[s.charAt(i)-'a']++;
    }
    for(int i=0;i<tLen;i++) {
        map[t.charAt(i)-'a']--;
        //map[t.charAt(i)-'a']<0:字元串t中的字元t.charAt(i)的個數大于s中的
        //是以t不是s的字母異位詞，直接傳回false即可
        if (map[t.charAt(i)-'a']<0) {
            return false;
        }
    }
    return true;
}