【九章斩题录】Leetcode：判定是否互为字符重排（C/C++）

    

---

面试题 01.02. 判定是否互为字符重排

✅ 模板：C++

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
 
    }
};

---

「 法一 」排序

💡 思路：看到题目中说 "重新排列后能否变成另一个字符串"，等等……重新排列？

我勒个豆，这题直接 sort 两下不就秒了？

排序完比对一下两个字符串是不是一样的就行了：

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        sort(s1.begin(), s1.end());   // 排s1
        sort(s2.begin(), s2.end());   // 排s2 
 
        return s1 == s2 ? true : false;   // 对比
    }
};

写完了，然后想了想应该可以再优化一下，如果长度不相等那必然不能重排。

而且好像也没必要用三目，直接 return 表达式就行。

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;   // 脑抽用三目，忘了可以直接返回了。
    }
};

哈哈哈搞定了，sort 排序时间复杂度为 O(nlogN)" role="presentation">O(nlogN)$O(nlogN)$，比较用了 O(n)" role="presentation">O(n)$O(n)$，所以时间复杂度为：

O(nlogN)+O(n)=O(nlogN)" role="presentation">O(nlogN)+O(n)=O(nlogN)$O(nlogN)+O(n)=O(nlogN)$

 用 sort 轻松将该题斩于马下……

---

「 法二 」HashMap！uh~

💡 思路：好像也可以用哈希，HHHHHHHHHash Map！ur！

分别 for 滚一轮 s1 和 s2 的元素：

• 统计字符串 s1 各字符数量，遇到 +1
• 统计字符串 s2 各字符数量，遇到 -1
• 遍历 s1, s2 中各字符的数量差，若 s1, s2 中某字符的数量不一致，则不互为重排。

如果都对上了，就是 "抵消" 了，看代码：

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) {   // 提前解决s1 s2长度不一样的情况
            return false;
        }
 
        unordered_map<char, int> hash;
        for (char e : s1) {   // 一边加
            hash[e] += 1;
        }
        for (char e : s2) {   // 另一边减
            hash[e] -= 1;
        }
 
        for (auto kv : hash) {
            if (kv.second != 0) {  
                return false;
            }
        }
 
        return true;
    }
};

在这里，我特别想感谢一下 auto for 的存在，如果没有 auto for，那么会非常的窒息……

for (unordered_map<char, int>::iterator it = hash.begin(); 
    \ it != hash.end(); it++) {
            if (it->second != 0) {
                return false;
            }
        }

喝完咖啡回来想了想，好像也不用再迭代器判断一遍，s2 的 for 当前元素 -1 后发现<0 的话就可以直接 return false 了，<0 肯定是因为 s1 里压根就没出现过这个字符 (没记录到哈希桶里)……   但这样就 必须要对 s1 和 s2 进行长度判断，长度不同直接 return false。

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
 
        unordered_map<char, int> hash;
        for (char& e : s1) {   // 一边加
            hash[e] += 1;
        }
        for (char& e : s2) {   // 另一边减
            hash[e] -= 1;
            if (hash[e] < 0) {
                return false;
            }
        }
 
        return true;
    }
};

测试，if (<0) 就不能重排。

s1 = a a b b c
s2 = a a b c c
入桶(+)：a:2  b:2  c:1    
检查(-)：a:0  b:1  c:-1
return false;
 
s1 = a b c
s2 = b c a
入桶(+)：a:1  b:1  c:1    
检查(-)：a:0  b:0  c:0
return true;
 
s1 = a b c
s2 = b a d
入桶(+)：a:1  b:1  c:1    
检查(-)：a:0  b:0  d:-1
return false;

也可以直接定义一个维护 128 个字符的数组：

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
 
        vector<int> table(128, 0);
 
        for (char& ch : s1) {
            table[ch]++;
        }
 
        for (char& ch : s2) {
            table[e]--;
            if (table[e] < 0) {
                return false;
            }
        }
 
        return true;
    }
};

​

📌 [ 笔者 ]   王亦优
📃 [ 更新 ]   2023.
❌ [ 勘误 ]   /* 暂无 */
📜 [ 声明 ]   由于作者水平有限，本文有错误和不准确之处在所难免，
              本人也很想知道这些错误，恳望读者批评指正！