网站开发与维护 专业sem竞价代运营公司
01.02、[简单] 判定是否互为字符重排
1、题目描述
给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
在这道题中，我们的任务是判断两个字符串 s1 和 s2 是否可以通过重新排列字符使得其中一个字符串变为另一个字符串。这意味着，我们需要检查这两个字符串是否包含完全相同的字符，并且每个字符的数量也必须相同。
2、方法一：排序比较法
2.1、思路解析
如果两个字符串是彼此的排列，那么对这两个字符串进行排序后，它们应该完全相同。因此，我们可以通过以下步骤来实现：
- 长度判断：首先，检查
s1和s2的长度。如果长度不同，直接返回false。 - 排序：对
s1和s2分别进行排序。 - 比较：比较排序后的两个字符串是否相等。如果相等，返回
true，否则返回false。
2.2、代码实现
class Solution {
public:bool CheckPermutation(string s1, string s2) {// 如果两个字符串长度不同，必然不能是彼此的排列if (s1.size() != s2.size()) {return false;}// 对两个字符串进行排序sort(s1.begin(), s1.end());sort(s2.begin(), s2.end());// 比较排序后的字符串是否相等return s1 == s2;}
};
3、方法二：哈希表计数法
3.1、思路解析
另一种方法是使用哈希表记录每个字符的出现次数。如果两个字符串是彼此的排列，那么每个字符在两个字符串中的出现次数必须相同。因此，我们可以通过以下步骤来实现：
- 长度判断：首先，检查
s1和s2的长度。如果长度不同，直接返回false。 - 字符计数：使用一个长度为 26 的数组
hash来记录s1中每个字符的出现次数，并在遍历s2的过程中减去相应字符的计数。 - 判断字符计数：如果在遍历
s2的过程中发现某个字符的计数小于 0，说明s2中包含了s1没有的字符，返回false。 - 返回结果：遍历结束后，如果所有字符的计数都为 0，返回
true。
3.2、代码实现
class Solution {
public:bool CheckPermutation(string s1, string s2) {// 如果两个字符串长度不同，必然不能是彼此的排列if (s1.size() != s2.size()) {return false;}// 使用哈希表记录每个字符的出现次数int hash[26] = {0};// 统计 s1 中每个字符的出现次数for (const auto& ch : s1) {hash[ch - 'a']++;}// 遍历 s2，减去相应字符的计数for (const auto& ch : s2) {hash[ch - 'a']--;// 如果发现某个字符的计数小于 0，返回 falseif (hash[ch - 'a'] < 0) {return false;}}// 如果遍历结束后没有发现问题，返回 truereturn true;}
};
4、总结
这两种方法都可以有效地判断两个字符串是否为彼此的排列。方法一使用排序比较，简单直观；方法二使用哈希表计数，时间复杂度更低。具体选择哪种方法，可以根据具体情况和需求来决定。