[算法] 判断是否为字符串重排(simple, 面试)

好的, 今天我们又是崭新的一天呐, 我们来分享一道很简单的题目 -> 判断是否为字符串重排

因为是简单 + 面试题的组合, 我们来一步一步走~
力扣有个题解写的不错, 在这里分享一下: 力扣题解链接

1. 题意

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

示例 1：
输入: s1 = “abc”, s2 = “bca”
输出: true

示例 2：
输入: s1 = “abc”, s2 = “bad”
输出: false
说明：

• 0 <= len(s1) <= 100
• 0 <= len(s2) <= 100

嗯, 这道题的意思大概就是给你俩字符串, 让你判断这俩字符串重新排一下字母顺序能否变成另一个字符串.

2. 思路

我们按照题目的意思, 直接暴力求解.
思路1: 暴力求解. 时间复杂度是O(N!)
  很简单, 就是直接把第一个字符串全排列一下, 依次与str2进行比较即可.
  如果一个字符串有 ( n ) 个字符，且所有字符都不同，那么全排列的数量为 ( n! )（n 的阶乘）。计算步骤如下：

  实际上, 我们完全没必要去真的全排列字符串str, 只需要记录两个字符串每个字符对应的个数, 然后比较是否一致即可.

思路2: 统计两个字符串中各字符个数是否一致

• 策略1: 统计字符个数 + 两个哈希表
• 策略2: 统计字符个数 + 一个哈希表
• 策略3: 统计字符个数 + 两个数组
• 策略4: 统计字符个数 + 一个数组

  很显然, 用两个哈希表做映射空间开销比用数组会大一些, 因此建议用数组.
  用一个数组比用两个数组更加节省空间, 因此用一个数组更好, 只需要判断数组中的值是否都为0即可.

但是这个地方还有个小细节: 如果两个字符串长度不一致, 则无需判断, 因为总的字符个数不一致, 更不能保证每个字符的个数都一致了!

3. 编码

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

        int hash[26] = { 0 };
        for(int i = 0; i < s1.size(); i++)
            hash[s1[i] - 'a'] += 1;
        for(int i = 0; i < s2.size(); i++)
        {
            hash[s2[i] - 'a'] -= 1;
            if(hash[s2[i] - 'a'] < 0) return false;
        }

        return true;
    }
};