Leetcode 242. Valid Anagram（有效的变位词）

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?

题目大意：

给定两个字符串s和t，写一个函数来确定t是不是s的一个变位词。

比如说：s="anagram", t="nagaram", 是

s="rat", t="car", 不是

注意：你可以假定字符串只含有小写字母。

进一步的：如果输入含有unicode字符呢？这样的情况怎么去适用你的解决方案呢？

解法一：排序后判相等

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

runtimes:80ms

复杂度为O(nlogn)；

解法二：哈希表，判断两个字符串相同字母的个数是否相等

 1 class Solution {
 2 public:
 3     bool isAnagram(string s, string t) {
 4         int  len_s = s.length(), len_t = t.length(), i, ns[26] = {0};
 5         //vector<int> ns(26, 0);
 6         
 7         for(i = 0; i < len_s; i++)
 8             ns[s[i] - 'a']++;
 9         for(i = 0; i < len_t; i++)
10             ns[t[i] - 'a']--;
11             
12         for(i = 0; i < 26; i++)
13             if(ns[i] != 0)
14                 return false;
15         return true;
16     }
17 };

runtimes:12ms

复杂度：O(n)