有效的字母异位词
本节对应代码随想录中:代码随想录,讲解视频:学透哈希表,数组使用有技巧!Leetcode:242.有效的字母异位词_哔哩哔哩_bilibili
习题
题目链接:242. 有效的字母异位词 - 力扣(LeetCode)
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词,s 和 t 仅包含小写字母。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
排序
先对两个字符串排序,然后就可以直接比较两个字符串是否相等
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
};
- 时间复杂度:O(nlogn)。其中 n 为字符串的长度。因为使用了排序函数,排序的时间复杂度为 O(nlogn)。字符串比较的时间复杂度为 O(n),因此总时间复杂度为 O(nlogn + n) = O(nlogn)。
- 空间复杂度:O(log n)。其中 n 为字符串的长度。排序需要使用 O(logn) 的栈空间,因此空间复杂度为 O(logn)。
我的解法
既然 s 和 t 都仅包含小写字母,那就可以分别定义两个数组,用来存对应字符的出现次数,如果两个数组对应位置的数值一样那就是 true。同时如果两个字符串长度不同,可以直接返回 false
class Solution {
public:
bool isAnagram(string s, string t) {
// 两个字符若长度不等直接返回false
int size = s.length();
if (size != t.length()) {
return false;
}
int num_s[26] = {
0};
int num_t[26] = {
0};
// 遍历字符串,两个计数的数组计数
for (int i = 0; i < size; i++) {
num_s[int(s[i]) - 97] += 1;
num_t[int(t[i]) - 97] += 1;
}
// 一旦某一个字符的次数不一样直接返回false
for (int i = 0; i < 26; i++) {
if (num_s[i] != num_t[i]) {
return false;
}
}
return true;
}
};
- 时间复杂度:O(n)。其中 n 为字符串的长度。遍历字符串需要 O(n) 的时间,计数数组的遍历需要 O(1) 的时间,因此总时间复杂度为 O(n)。
- 空间复杂度:O(1)。由于只使用了长度为 26 的计数数组,空间复杂度是常数级别的。
可以优化的点
int(s[i]) - 97
可以替换为s[i] - 'a'
,这样无需记住字符 a 的 ASCII
哈希表
其实我的解法也属于哈希表,不过其实不需要两个数组来计数,只需要一个数组统计其中一个字符串,然后遍历另一个字符串的时候对应位置的数值减1,如果对应位置数值<0,说明 t 的这个位置的元素比 s 的多,则返回 false
例如,s 为 aab,t 为 aaa。遍历到 t 的第二个 a 的时候,table[0]已经等于0了,当遍历到 t 的第三个 a 的时候,table[0]=-1<0,说明 t 中的 a 比 s 中的 a 至少多一个(后面可能还会有更多的 a,但没必要再去遍历了)。
代码随想录中是先遍历 t,对应位置减1,再判断数组是否全为0,但下面这种解法只需使用两个 for 循环,比代码随想录上的3个 for 循环更优
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
int table[26] = {
0};
// 数组计数
for (int i = 0; i < s.length(); i++) {
table[s[i] - 'a']++;
}
for (int i = 0; i < t.length(); i++) {
// 遍历字符串t对应位置减1
table[t[i] - 'a']--;
// 如果<0说明这个位置t的比s的多,即多减了一次
if (table[t[i] - 'a'] < 0) {
return false;
}
}
return true;
}
};
- 时间复杂度:O(n)。其中n为字符串的长度,需要遍历两个字符串,以及进行常数次的数组操作。
- 空间复杂度:O(1)。因为使用了一个大小为26的数组来存储每个字母出现的次数,空间大小与输入的字符串长度无关。
进阶解法
如果输入字符串包含 unicode 字符,那么可能的字符就不再是26个,没法使用大小为26的数组进行计数。此时就需要使用 unordered_map 了。
思路和上面的哈希表的差不多,先遍历 s,将其每个元素放进哈希表中。再遍历字符串 t,如果某个元素的次数<0说明 t 的这个位置的元素比 s 的多,则返回 false。只不过哈希表解法计数是根据字符-a 找索引,而这个是根据 key 直接找索引
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) {
// 先判断两个字符串长度是否相同
return false;
}
unordered_map<char, int> hash; // 定义哈希表
for (int i = 0; i < s.size(); i++) {
// 遍历一个字符串
hash[s[i]]++; // 把s的每个字符放进哈希表中
}
for (int i = 0; i < t.size(); i++) {
hash[t[i]]--; // 在hash表中抵消该字符次数
if (hash[t[i]] < 0) {
return false;
}
}
return true; // 若出现次数都一致,则返回true
}
};
- 时间复杂度:O(n)。其中n为字符串的长度,需要遍历两个字符串,并对哈希表进行常数次操作。
- 空间复杂度:O(n)。因为哈希表中最多存储 n 个字符,所以空间复杂度与输入的字符串长度有关。