LeetCodeその2：ValidAnagram

自分の解答1

2つの文字がアナグラムになっているかを判定する問題。

Accept

   public boolean isAnagram(String s, String t) {

        // 文字数が違う場合はfalse
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();

        // 文字をKey　数をValueとしてMapに格納
        for (int i = 0; i < s.length(); i++) {
            char char1 = s.charAt(i);

            // 既に格納済みの文字ならスキップ
            if (map.containsKey(char1)) {
                continue;
            }

            int count = 1;
            for (int j = i + 1; j < s.length(); j++) {
                if (char1 == s.charAt(j)) {
                    count++;
                }
            }
            map.put(char1, count);
        }

        // 同上
        for (int i = 0; i < t.length(); i++) {
            char char1 = t.charAt(i);

            // 既に格納済みの文字ならスキップ
            if (map2.containsKey(char1)) {
                continue;
            }

            int count = 1;
            for (int j = i + 1; j < t.length(); j++) {
                if (char1 == t.charAt(j)) {
                    count++;
                }
            }
            map2.put(char1, count);
        }


        // アナグラム判定
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {

            // 同じ単語
            if(map2.containsKey(entry.getKey())) {
                
                // 同じ単語で違う個数
                if(entry.getValue().equals(map2.get(entry.getKey())) == false) {
                    return false;
                }
                
            // 同じ単語が1個もない
            } else {
                return false;
            }
        }
        return true;
    }

自分の解答2

ちょっとコードをきれいにした。

Accept

   // 自分の解答2
    public boolean isAnagram2(String s, String t) {

        // 文字数が違う場合はfalse
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Integer> map = new HashMap<>();
        Map<Character, Integer> map2 = new HashMap<>();

        // 文字をKey　数をValueとしてMapに格納
        for (int i = 0; i < s.length(); i++) {
            char char1 = s.charAt(i);

            // 既に格納済みの文字ならスキップ
            if (map.containsKey(char1)) {
                continue;
            }

            int count = 1;
            for (int j = i + 1; j < s.length(); j++) {
                if (char1 == s.charAt(j)) {
                    count++;
                }
            }
            map.put(char1, count);
        }

        // 同上
        for (int i = 0; i < t.length(); i++) {
            char char1 = t.charAt(i);

            // 既に格納済みの文字ならスキップ
            if (map2.containsKey(char1)) {
                continue;
            }

            int count = 1;
            for (int j = i + 1; j < t.length(); j++) {
                if (char1 == t.charAt(j)) {
                    count++;
                }
            }
            map2.put(char1, count);
        }


        // アナグラム判定
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {

            // 同じ単語
            if(map2.containsKey(entry.getKey())) {//containsKeyにして2重ループをやめた。ちょっとスッキリ。
                
                // 同じ単語で違う個数
                if(entry.getValue().equals(map2.get(entry.getKey())) == false) {
                    return false;
                }
                
            // 同じ単語が1個もない
            } else {
                return false;
            }
        }
        return true;
    }

模範解答

理解するのに時間かかった。

コメントで解説。

class Solution {

    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;

        int[] store = new int[26];//a～zの数が26文字なので26要素分の配列を用意

                    /** 例えば s t の1文字目が両方「a」の場合
                    * aを数値にすると97になるので
                    * store[97 - 97] = store[0]++
                    * store[97 - 97] = store[0]-- 
                    * = store[0] = 0
                    * 
                    * もし1文字目 s が「a」 tが「b」の場合は
                    * store[97 - 97] = store[0]++
                    * store[98 - 97] = store[0]-- 
                    *   store[0] = 1
                    *   store[1] = -1
                    * になる。
                    * 
                    * なのでstore配列の要素が全て0ならTRUE
                    * store[0～25] = 0 ならTRUE
                    * 
                    *  **/
        for (int i = 0; i < s.length(); i++) {
            store[s.charAt(i) - 'a']++;
            store[t.charAt(i) - 'a']--;
        }

        for (int n : store) if (n != 0) return false;

        return true;
    }
}

・引用元
leetcode/0242-valid-anagram.java at main · neetcode-gh/leetcode · GitHub

ちょっとずるいやつ

動画解説ではコーディング面接では通らないだろうと言ってた。

面接官は自分で考えたソートアルゴリズムを見たいだろうから。

仕事ならこれが良い。

   public boolean isAnagram(String s, String t) {

        char[] charArray1 = s.toCharArray();
        char[] charArray2 = t.toCharArray();
        
        Arrays.sort(charArray1);
        Arrays.sort(charArray2);
        
        return Arrays.equals(charArray1, charArray2);
    }