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
    
      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.