ValidAnagram [source code]

public class ValidAnagram {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        if (s.equals("") && t.equals("")) return true;

        char[] charS = s.toCharArray(), charT = t.toCharArray();
        int[] counts = new int[26];
        for (char c : charS) counts[c - 'a']++;
        for (char c : charT) counts[c - 'a']--;
        for (int i : counts) if (i != 0) return false;
        return true;
    }

    public static void main(String[] args) {
        ValidAnagram tester = new ValidAnagram();
        String[] input1 = {"anagram", "nagaram"};
        assert tester.isAnagram(input1[0], input1[1]) == true;
        String[] input2 = {"", ""};
        assert tester.isAnagram(input2[0], input2[1]) == true;
        assert tester.isAnagram("rat", "car") == false;
        assert tester.isAnagram("aa", "bb") == false;
        assert tester.isAnagram("aabb", "bbaacc") == false;
    }
}

这个算法最开始想到的解法就是用Single Number那种pair eliminatio的思路来做, 不过这个其实是这个题目的一个 beartrap, 因为pair elimination那个判断的前提是, 所有的 duplicate 出现不超过两次. 这个题目, 如果是"aa", "bb"这样的 input, 那么就可以逃过single number的算法, 但是却不是正确的答案;

除开这个小插曲, 这个题目总体还是很简单的, 一个标准的 count 类历史信息题目. 一个小的优化, 就是利用类似moore voting的概念, 不是维护两个 counts 然后进行比较, 而是用s 来投支持票, t 来投反对票这样的思路来做;

最后的速度是4ms, 89%, 可以接受.

submission最优解貌似跟我这个算法一模一样.
editorial 最优解还不如我这个;
discussion里面看到一个追加的优化: 因为其实我们已经保证了 s 和 t 的长度相等, 所以其实过 s 和 t 的两个 pass 可以合并到一个 pass 里面; 除此以外, discussion的最优解也好不过这个;

另外一个 suboptimal 的思路就是用 sorting, 两个 sort 之后判断 equals. 这个做法比较简单直接, 也反映了 sorting 在 array 类问题很多时候都可以大幅降低问题难度;

另外注意这里 emptycase 的处理, 第一行保证了长度一定相等之后, 后面就不需要判断 s 和 t 两者之间只有一个为 null 的情况了;

return (lettersS[0] ^ lettersT[0]) == 0 ? true : false;

注意这里的这个括号不能少, xor 的优先级非常低;

另外这个问题的empty case的处理非常重要, 否则直接就报错了;

Problem Description

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = "anagram", t = "nagaram", return true.
s = "rat", t = "car", return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

Difficulty:Easy
Category:Algorithms
Acceptance:46.06%
Contributor: LeetCode
Companies
amazon uber yelp
Related Topics
hash table sort
Similar Questions
Group Anagrams Palindrome Permutation Find All Anagrams in a String