C++算法练习-day11——242.有效的字母异位词
题目来源：. - 力扣（LeetCode）
题目描述
题目要求判断两个字符串 s 和 t 是否为字谜（Anagram）。字谜指的是两个字符串包含相同数量的相同字符，只是字符的顺序可能不同。例如，"listen" 和 "silent" 是字谜，而 "hello" 和 "world" 不是。
思路分析
-
长度检查：首先，如果两个字符串的长度不同，它们一定不是字谜。因此，第一步是检查字符串的长度是否相等。
-
字符计数：如果长度相等，我们可以使用一个固定大小的数组（或哈希表）来记录每个字符出现的次数。由于题目没有指明字符集，我们可以假设只包含小写字母（'a' 到 'z'）。
-
增减计数：遍历字符串
s，对每个字符的计数加一；遍历字符串t，对每个字符的计数减一。如果两个字符串是字谜，那么最后所有字符的计数都应该为零。 -
检查结果：最后，检查计数数组是否全部为零。
代码实例
#include <vector>
#include <string> class Solution {
public: bool isAnagram(std::string s, std::string t) { // 如果两个字符串的长度不同，直接返回false if (s.size() != t.size()) { return false; } int n = s.size(); // 创建一个大小为26的数组，用于记录字符'a'到'z'的计数 std::vector<int> res(26, 0); // 遍历字符串s，对每个字符的计数加一 for (int i = 0; i < n; i++) { res[s[i] - 'a']++; } // 遍历字符串t，对每个字符的计数减一 for (int i = 0; i < n; i++) { res[t[i] - 'a']--; } // 检查计数数组是否全部为零 for (int i = 0; i < 26; i++) { if (res[i] != 0) { return false; } } // 如果所有字符的计数都为零，返回true return true; }
};主函数：
#include <iostream> int main() { Solution sol; std::string s = "listen"; std::string t = "silent"; if (sol.isAnagram(s, t)) { std::cout << s << " 和 " << t << " 是字谜。" << std::endl; } else { std::cout << s << " 和 " << t << " 不是字谜。" << std::endl; } return 0;
}
知识点摘要
-
字符串长度检查：判断两个字符串是否等长的基本方法。
-
字符计数：使用固定大小的数组或哈希表来记录字符出现的次数，这种方法在处理字符集固定且范围较小的情况时非常高效。
-
数组索引计算：通过字符的ASCII值减去某个基准值（如'a'的ASCII值）来计算数组索引，是一种常用的字符映射技巧。
-
遍历与计数：通过遍历字符串并对字符进行计数，是处理字符串问题的常用方法。
这种方法的时间复杂度为O(n)，其中n是字符串的长度，因为我们只遍历了两个字符串各一次。空间复杂度为O(1)，因为我们使用了固定大小的数组（26个字母）。