Program

Write a method anagram(s,t) to decide if two strings are anagrams or not.

Example

Given s="abcd", t="dcab", return true.

Challenge

O(n) time, O(1) extra space

Note

建立一个长度为256的数组，统计所有256个字符在String s出现的次数，然后减去这些字符在String t中出现的次数。若某个字符统计次数最终小于0，说明t中这个字符比s中更多，返回false。否则，循环结束，说明所有字符在s和t中出现的次数一致，返回true。

Solution

Brute Force

O(nlogn)

public class Solution {
    public boolean isAnagram(String s, String t) {
        char[] schar = s.toCharArray();
        char[] tchar = t.toCharArray();
        Arrays.sort(schar);
        Arrays.sort(tchar);
        return String.valueOf(schar).equals(String.valueOf(tchar));
    }
}

HashMap

public class Solution {
    public boolean anagram(String s, String t) {
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[(int) s.charAt(i)]++;
        }
        for (int i = 0; i < s.length(); i++) {
            count[(int) t.charAt(i)]--;
            if (count[(int) t.charAt(i)] < 0) return false;
        }
        return true;
    }
}

Slow HashMap

public class Solution {
    public boolean isAnagram(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (map.containsKey(ch)) {
                map.put(ch, map.get(ch)+1);
            }
            else map.put(ch, 1);
        }
        for (int i = 0; i < t.length(); i++) {
            Character ch = t.charAt(i);
            if (!map.containsKey(ch)) return false;
            map.put(ch, map.get(ch)-1);
            if (map.get(ch) < 0) return false;
        }
        for (int i = 0; i < s.length(); i++) {
            Character ch = s.charAt(i);
            if (map.get(ch) != 0) return false;
        }
        return true;
    }
}

Follow up: contains unicode chars?

Just give the count[] array space of 256.