leetcode解题: Valid Anagram (242)

发表于 | 分类于

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,
s = “anagram”, t = “nagaram”, return true.
s = “rat”, t = “car”, return false.

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

解法1：Sort O(NlogN)

先排序，然后看排过序的两个string是否一致。

C++

主要是掌握一下两个c++里的用法:
一个是对于字符串的排序。
std::sort(s.begin(), s.end())
另一个是比较两个字符串用s1.compare(s2)的形式，当两个字符串相等时，返回0

1
2
3
4
5
6
7
8
9
class Solution {
public:
    bool isAnagram(string s, string t) {
        std::sort(s.begin(), s.end());
        std::sort(t.begin(), t.end());
        return s.compare(t) == 0;
    }
};

Java

1

解法2：Hashtable O(N) time + O(N) Space

统计其中一个字符串每个字符出现的次数，然后扫描另一个字符串来判断是否一致。
如果都是a-z的小写字母，那就只需要一个大小为26的数组记录就可，如果出现了unicode，那么还是必须要用hashtable来解决。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool isAnagram(string s, string t) {
        unordered_map<char,int> map;
        for (char c : s) {
            ++map[c];
        }
        for (char c: t) {
            --map[c];
            if (map[c] < 0) {
                return false;
            }
        }
        // check if there's remaining
        for (auto iter = map.begin(); iter != map.end(); ++iter) {
            if (iter->second != 0) {
                return false;
            }
        }
        return true;
    }
};

Java

1

Follw up

见解法2的讨论，主要是针对用hashtable这一种用法的follow up。