文章目录
242. 有效的字母异位词
题目描述
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
提示:
- 1 <= s.length, t.length <= 5 * 104
- s 和 t 仅包含小写字母
进阶: 如果输入字符串包含 unicode 字符怎么办?你能否调整你的解法来应对这种情况?
c++代码
代码执行流程如下:
- 首先,通过比较两个字符串 s 和 t 的长度,如果它们长度不相等,则直接返回 false,因为不同长度的字符串不可能是异位词。
- 声明两个长度为26的整型数组 a 和 b,用于计算每个字符串中每个字母的出现频率。这里使用一个小技巧:由于题目说明只包含小写字母,可以通过减去 ‘a’ 的 ASCII 值将字母的 ASCII 值映射到一个 0 到 25 的范围内,这样 a[0] 就对应 ‘a’ 的出现次数,a[1] 对应 ‘b’ 的出现次数,以此类推。
- 使用两个独立的循环分别遍历字符串 s 和 t,并递增 a 和 b 数组中相应字母计数器的值。
- 使用一个循环比较两个计数器数组 a 和 b 的每一个元素。如果所有元素都相等,则说明 s 和 t 有相同的字符和频率,可以认为它们是异位词,函数返回 true。如果有任何一个元素不相等,函数返回 false。
进阶情况
对于包含 Unicode 字符的字符串,我们不能仅仅使用长度为26的数组来计数,因为 Unicode 字符集非常大。一个可能的解决方案是使用 unordered_map(或 map,取决于性能要求)来动态地存储每个字符及其出现的次数。这样我们就可以支持所有 Unicode 字符,而不仅限于26个小写英文字母。
class Solution {
public:
bool isAnagram(string s, string t) {
// 如果两个字符串长度不同,它们不能是异位词
if(s.size() != t.size()) return false;
// 声明两个长度为26的数组来计数字母出现频率
// 英文字母表大小为26
int a[26] = {
0}, b[26] = {
0};
// 遍历字符串s,统计每个字母出现的次数
for(int i = 0; i < s.size(); i++)
a[s[i] - 'a']++; // 'a'的ASCII码作为偏移量,将字母映射到0-25的范围
// 遍历字符串t,统计每个字母出现的次数
for(int i = 0; i < t.size(); i++)
b[t[i] - 'a']++; // 同上
// 比较两个数组的内容是否完全一致
for(int i = 0; i < 26; i++)
// 如果在某个字母的计数不同,则不是异位词
if(a[i] != b[i])
return false;
// 如果所有字母计数都相同,则是有效的异位词
return true;
}
};