题目描述

题目链接：242. Valid Anagram

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

例子

例子 1

Input: s = “anagram”, t = “nagaram” Output: true

例子 2

Input: s = “rat”, t = “car” Output: false

Follow Up

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

Note

You may assume the string contains only lowercase alphabets.

解题思路

方法一

首先比较两个字符串的长度是否一致，不一致的话可以首先排除。然后通过哈希表记录其中一个字符串出现的字符数量，接下来遍历第二个字符串的字符并在哈希表执行以下操作：

• 如果哈希表没有记录该字符或者该字符的数量为 0，返回 false
• 哈希表中该字符数量 - 1，遍历下一个字符

代码如下：

#include <string>
#include <unordered_map>

class Solution {
public:
    bool isAnagram(std::string s, std::string t) {
        if (s.length() != t.length()) return false;
        std::unordered_map<char, int> count;
        for (char letter: s) {
            if (count.find(letter) == count.end()) {
                count[letter] = 0;
            }
            count[letter]++;
        }
        for (char letter: t) {
            if (count.find(letter) == count.end() || count[letter] == 0) return false;
            count[letter]--;
        }
        return true;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1) 字符数量为常数

方法二

也可以通过给两个字符串各自排序，并依次比较对应位置字符是否一致。代码比较简单就不写了。

• 时间复杂度: O(nlogn)
• 空间复杂度: O(1) 字符数量为常数