Valid Anagram

Description

Write a method anagram(s,t) to decide if two strings are anagrams or not.Have you met this question in a real interview? Yes

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

所谓 anagram, 就是两个词所用的字母及其个数都是一样的，但是，字母的位置不一样。比如 abcc 和 cbca 就是 anagram.

Java里，把char直接放进int[]里是可以的，c++要进行char - ‘a’的操作

这道题要求o(1) extra space，关于O(1) space, 在网上找的解释：

Let's say I create some data structure with a fixed size, and no matter what I do to the data structure, it will always have the same fixed size. Operations performed on this data structure are therefore O(1).

An example, let's say I have an array of fixed size 100. Any operation I do, whether that is reading from the array or updating an element, that operation will be O(1) on the array. The array's size (and thus the amount of memory it's using) is not changing.

Another example, let's say I have a LinkedList to which I add elements to it. Every time I add an element to the LinkedList, that is a O(N) operation to the list because I am growing the amount of memory required to hold all of it's elements together.

public class Solution {
    /**
     * @param s: The first string
     * @param t: The second string
     * @return: true or false
     */
    public boolean anagram(String s, String t) {
        // write your code here
        
        
        if(s.length() != t.length()){
            return false;
        }
        
        int[] count = new int[256];
        
        for (int i = 0; i < s.length(); ++i ){
            count[s.charAt(i)]++;
        } 
        for (int i = 0; i < t.length(); ++i ){
            if(--count[t.charAt(i)] < 0) return false;
        }
        
        return true;
        
    }
}