Two Strings Are Anagrams 158

Question

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

Clarification

What is Anagram?

• Two strings are anagram if they can be the same after change the order of characters.

Example

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

Given s = "ab", t = "ab", return true.

Given s = "ab", t = "ac", return false.

Challenge

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

Solution

思想很简单，用256长度的字符数组存所有字符的个数。先遍历s，将s中每个字符及其个数记录下来。然后再遍历t，每遇到一个字符，就去字符数组的对应位置－1，如果出现负数，则返回false。

要先讨论几种corner case：是否为null，长度是否相等

代码如下：

public class Solution {
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    public boolean anagram(String s, String t) {
        // write your code here
        if(s == null && t == null){
            return true;
        }

        if(s == null || t == null){
            return false;
        }

        if(s.length() != t.length()){
            return false;
        }

        //有256个character
        int[] count = new int[256];
        for (int i = 0; i < s.length(); i++) {
            count[(int) s.charAt(i)]++;
        }
        for (int i = 0; i < t.length(); i++) {
            count[(int) t.charAt(i)]--;
            if (count[(int) t.charAt(i)] < 0) {
                return false;
            }
        }
        return true;
    }
};