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

题目描述

思路

思路1：哈希表

1.若两个字符串长度不相等，则一定不符合题意；
2.创建一个map集合，先将字符串s1中的每一个字符与其对应的数量存入集合（字符作为键、其对应的数量作为值）；
3.再对于字符串s2，将其字符对应的值依次减去；
4.最后判断map集合中的每一个值，若存在不为0的键则不符合；

思路2：位图

和思路1类似，我们可以直接使用一个数组，作为位图将26个小写字母（题目中说到只包含小写字母）与其对应的个数存入到数组中(与思路1思路类似，也是一个数组加，一个数组减)

复杂度

思路1与2均如下
时间复杂度:

$O(n)$

空间复杂度:

$O(n)$

Code

思路1：

class Solution {
public:
    /**
     * bitmap
     *
     * @param s1 Given word1
     * @param s2 Given word2
     * @return bool
     */
    bool CheckPermutation(string s1, string s2) {
        int s1Len = s1.length();
        int s2Len = s2.length();
        if (s1Len != s2Len) {
            return false;
        }
        vector<int> alphabet(26);
        for (int i = 0; i < s1Len; ++i) {
            alphabet[s1.at(i) - 97]++;
            alphabet[s2.at(i) - 97]--;
        }
        for (int i = 0; i < alphabet.size(); ++i) {
            if (alphabet[i] != 0) {
                return false;
            }
        }
        return true;
    }
};

思路2：

class Solution {
public:
    /**
     *  Map
     *
     * @param s1 Given word1
     * @param s2 Given word2
     * @return bool
     */
    bool CheckPermutation(string s1, string s2) {
        int s1Len = s1.length();
        int s2Len = s2.length();
        if (s1Len != s2Len) {
            return false;
        }
        unordered_map<char, int> map;
        for (char c: s1) {
            map[c] += 1;
        }
        for (char c: s2) {
            map[c] -= 1;
        }
        for (auto kv: map) {
            if (kv.second != 0) {
                return false;
            }
        }
        return true;
    }
};