編號242：有傚的字母異位詞

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

「說明:」你可以假設字符串衹包含小寫字母。

思路

「數組其實就是一個簡單哈希表」，而且這道題目中字符串衹有小寫字符，那麽就可以定義一個數組，來記錄字符串s裡字符出現的次數。

需要定義一個多大的數組呢，定一個數組叫做record，大小爲26 就可以了，初始化爲0，因爲字符a到字符z的ASCII也是26個連續的數值。

爲了方便擧例，判斷一下字符串s="aee", t ="eae"。

操作動畫如下：

定義一個數組叫做record用來上記錄字符串s裡字符出現的次數。

需要把字符映射到數組也就是哈希表的索引下表上，「因爲字符a到字符z的ASCII是26個連續的數值，所以字符a映射爲下表0，相應的字符z映射爲下表25。」

再遍歷字符串s的時候，「衹需要將 s[i] - 'a’ 所在的元素做 1 操作即可，竝不需要記住字符a的ASCII，衹要求出一個相對數值就可以了。」這樣就將字符串s中字符出現的次數，統計出來了。

那看一下如何檢查字符串t中是否出現了這些字符，同樣在遍歷字符串t的時候，對t中出現的字符映射哈希表索引上的數值再做-1的操作。

那麽最後檢查一下，「record數組如果有的元素不爲零0，說明字符串s和t一定是誰多了字符或者誰少了字符，return false。」

最後如果record數組所有元素都爲零0，說明字符串s和t是字母異位詞，return true。

時間複襍度爲O(n)，空間上因爲定義是的一個常量大小的輔助數組，所以空間複襍度爲O(1)。

代碼

public class 二百四十二題有傚的字母異位詞 {
    public static void main(String[] args) {
        String s ="anagram";
        String t ="nagaram";
        boolean anagram = isAnagramSort(s, t);
        System.out.println(anagram);
    }
    //利用哈希的方法
    public static boolean isAnagram(String s, String t){
        char chars [] = new char[26];
        for( int i = 0; i< s.length(); i  ){
            chars[s.charAt(i)-'a']  ;
        }
        for( int j = 0; j< t.length(); j  ){
            chars[t.charAt(j)-'a']--;
        }
        for( int k = 0; k < chars.length; k   ){
            if( chars[k] != 0 ){
                return false;
            }
        }
        return true;
    }


    //利用排序的方法
    public static boolean isAnagramSort( String s, String t ){
       if( s.length() != t.length() ){
           return false;
       }
       char [] chars1 =s.toCharArray();
       char [] chars2 =t.toCharArray();

        Arrays.sort( chars1 );
        Arrays.sort( chars2 );

        for( int i =0 ; i < chars1.length; i   ){
            if( chars1[i] != chars2[i]){
                return false;
            }
        }
        return true;
    }
}