LintCode: Two Strings Are Anagrams

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

In string type problems, we always need to remember considering the space, upper case(capital) and lower case.

Tips: 
http://www.geeksforgeeks.org/g-fact-86/
baidu--time complexity

Auxiliary Space is the extra space or temporary space used by an algorithm.

Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input.

<way1> Store the letter frequency
1) Store the letters of two words in an array(ASICII 256). Position corresponds char and value corresponds to times letter appears in the word. Then just compare two array.
Time complexity: O(n) + O(n) + O(n) = O(n)
space complexity: O(1) + O(1) = O(1)
http://www.cnblogs.com/EdwardLiu/p/4427467.html

class Solution {
public:
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    bool anagram(string s, string t) {
        if(s.size() != t.size()) return false;
        int m1[256] = {0};
        int m2[256] = {0};
        for(int i = 0; i < s.size(); i++){
            m1[s[i]]++;
            m2[t[i]]++;
        }
        for(int i = 0; i < 256; i++){
            if(m1[i] != m2[i]) return false;
        }
        return true;
    }
};

2) Store the chars of two strings in an hashmap(unordered_map). Then compare this two maps with ==. [ ] will insert new element automatically.
Time and space Complexity is same with way 1
But it is not a O(1) extra space solution.
http://blog.xiaohuahua.org/2015/01/28/lintcode-two-strings-are-anagrams/
when I try to use make_pair(), cannot pass lintcode test. Weird.

class Solution {
public:
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    bool anagram(string s, string t) {
        // write your code here
        if(s.size() != t.size()) return false;
        unordered_map<char, int> map1, map2;
        for(int i = 0; i < s.size(); i++){
            map1[s[i]]++;
            map2[t[i]]++;
        }
        if(map1 == map2) return true;
        return false;
    }
};

<way 2> Sorting the letters
Sorting the letters of two strings first, then compare the sorted strings. We can use the sort() function directly in <algorithm> library. STL sort
http://www.code123.cc/docs/leetcode-notes/string/two_strings_are_anagrams.html
http://blog.csdn.net/tommyzht/article/details/45920113
Time complexity: Sorting O(nlogn) + Comparison O(n) = O(nlogn)
Space complexity: O(n) ?

class Solution {
public:
    /**
     * @param s: The first string
     * @param b: The second string
     * @return true or false
     */
    bool anagram(string s, string t) {
        if(s.size() != t.size()) return false;
        sort(s.begin(), s.end());
        sort(t.begin(), t.end());
        for(int i = 0; i < s.size(); i++){
            if(s[i] != t[i]) return false;
        }
        return true;
    }
};