leetocde：判断是否为字符重排

题目

给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

例：

  1. 输入: s1 = "abc", s2 = "bca"
  2. 输出: true

解答 & 代码

解法一：散列表

时间复杂度为 O(N)（其中 N = len(s1) + len(s2)），空间复杂度为 O(len(s1))

思想：两个字符串若能重排，则它们包含的 字符 以及 各字符的个数 应该相同

  • 先建立哈希表（散列表），用于存储字符串 s1 中各个 <字符，该字符出现的次数> 键值对
  • 遍历字符串 s1
    • 如果当前字符在哈希表中存在，则其对应的值 +1
    • 如果当前字符在哈希表中不存在，则将 <该字符，1> 插入哈希表
  • 遍历字符串 s2
    • 如果当前字符在哈希表中存在，则其对应的值 -1。如果值变为 0，则在哈希表中删除该字符
    • 如果当前字符在哈希表中不存在，则退出循环
  • 如果未遍历完字符串 s2 就退出，则说明两个字符串包含的字符不相同，不能互为重排；否则可以为重排 ```cpp

    include

class Solution { public: bool CheckPermutation(string s1, string s2) { if(s1.size() != s2.size()) return false;

    unordered_map<char, int> ch_cnt_map;
    for(int i = 0; i < s1.size(); i++)
    {
        if(ch_cnt_map.find(s1[i]) == ch_cnt_map.end())
        {
            ch_cnt_map.insert(make_pair(s1[i], 1));
        }
        else
        {
            ch_cnt_map[s1[i]] ++;
        }
    }

    int i;
    for(i = 0; i < s2.size() && ch_cnt_map.find(s2[i]) != ch_cnt_map.end(); i++)
    {
        ch_cnt_map[s2[i]] --;
        if(ch_cnt_map[s2[i]] == 0)
            ch_cnt_map.erase(s2[i]);
    }

    if(i < s2.size())
        return false;
    else
        return true;
}

};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户 内存消耗：6 MB, 在所有 C++ 提交中击败了 40.34% 的用户


<a name="IHNit"></a>
## 解法二：先排序
时间复杂度为 O(Nlog(N))，空间复杂度为 O(1)。（需使用堆排序，其他排序算法的复杂度更高）

思想：先将两个字符串排序，再逐元素比较连个字符串的元素是否相同

下面用了快排，时间复杂度为 O(Nlog(N))，空间复杂度为 O(log(N))

- 注意各函数的 string 传参要传引用，即 `string &s`
```cpp
// 快排的标准分各函数
int Partition(string &s, int low, int high)
{
    int pivot = s[low];
    while(low < high)
    {
        while(low < high && s[high] >= pivot)
        {
            --high;
        }
        s[low] = s[high];
        while(low < high && s[low] <= pivot)
        {
            ++low;
        }
        s[high]= s[low];
    }
    s[low] = pivot;
    return low;
}

// 快排
void QuickSort(string &s, int low, int high)
{
    if(low < high)
    {
        int pivot = Partition(s, low, high);
        QuickSort(s, low, pivot - 1);
        QuickSort(s, pivot + 1, high);
    }
}

// 排序
void Sort(string &s)
{
    QuickSort(s, 0, s.size() - 1); // 排序下标 0 ~ size-1 对应的字符
}

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if(s1.size() != s2.size())
            return false;

        Sort(s1);
        Sort(s2);
        if(s1 == s2)
            return true;
        else
            return false;
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6 MB, 在所有 C++ 提交中击败了 64.58% 的用户