每日leetcode

242. 有效的字母异位词 - 力扣（LeetCode）

题目

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词（字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次）。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

思路

1. 用哈希表存第一个字符串的字符出现次数，再遍历第二个字符串做减法，如果出现第二个字符串中有第一个字符串没有的字符，直接返回false。

代码实现

class Solution {
public:bool isAnagram(string s, string t) {unordered_map<char, int> letter_table;int ns = s.length(), nt = t.length();if(ns != nt) return false;for(int i = 0; i < ns; ++i) {if(letter_table.count(s[i]) == 0) letter_table[s[i]] = 1;else ++letter_table[s[i]];}for(int i = 0; i < nt; ++i) {if(letter_table.count(t[i])==0) return false;else {--letter_table[t[i]];}}for(unordered_map<char, int>::iterator it = letter_table.begin(); it != letter_table.end(); ++it) {if(it->second != 0) return false;}return true;}
};

复杂度分析

• 时间复杂度：三次循环的时间复杂度从上到下分别是O(n1)、O(n2)、O(c)（C为出现的字符集规模），所以总的时间复杂度是O(n1+n2)。——ps.看完别人的题解后才想起来n1和n2若开始循环时必然相等，所以时间复杂度应该是O(n)的。
• 空间复杂度：空间复杂度取决于哈希集合的大小，为O(c)。

题解

• 果然还是有优化空间的，既然前面已经判断了两字符串长度是否相等，那么其实s和t的统计可以同时进行，这样就少一次循环（好吧其实计算时间也是一样的，但是看起来好看一点）。