2.判定是否互为字符重排.md

题目

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

示例 1：

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

示例 2：

输入: s1 = "abc", s2 = "bad"
输出: false

思路以及解答

这是一道比较简单的题目，但是我们可以多想想一些解法：

1. 先排序再比较

既然需要对比是不是重排后的字符串，那么我们把两个字符串都按照相同的规则排序，排序完之后再挨个对比，就可以判断两个字符串是不是互为重排字符串了。

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1 == null && s2 == null) {
            return true;
        }
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        Arrays.sort(chars1);
        Arrays.sort(chars2);
        for (int i = 0; i < chars1.length; i++) {
            if (chars1[i] != chars2[i]) {
                return false;
            }
        }
        return true;
    }
}

上面的方式不仅使用了额外的空间，还用了排序算法，空间复杂度为 O(n), 时间复杂度为 O(nlogn + n)，排序算法为 O(nlogn)，但是遍历的时间复杂度为 O(n)。

2. 统计数值

其实，我们不需要排序，如果重排，我们只需要统计每个字符出现的次数即可，两个字符串出现的字符数量是不一致的话，那么肯定不是重排的。

下面我们使用 HashMap 来统计每一个字符出现的次数：

import java.util.HashMap;
import java.util.Map;

public class Solution2 {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1 == null && s2 == null) {
            return true;
        }
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        Map<Character, Integer> count1 = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            if (count1.get(s1.charAt(i)) != null) {
                count1.put(s1.charAt(i), count1.get(s1.charAt(i)) + 1);
            } else {
                count1.put(s1.charAt(i), 1);
            }
        }
        Map<Character, Integer> count2 = new HashMap<>();
        for (int i = 0; i < s2.length(); i++) {
            if (count2.get(s2.charAt(i)) != null) {
                count2.put(s2.charAt(i), count1.get(s2.charAt(i)) + 1);
            } else {
                count2.put(s2.charAt(i), 1);
            }
        }

        for (Map.Entry<Character, Integer> entry : count1.entrySet()) {
            if (count2.get(entry.getKey()) != entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}

没有了排序，时间复杂度下降了，时间复杂度和空间复杂度都是 O(n)。

3. 数组优化空间，提前返回结果

上面用的是 HashMap，其实我们可以用更加轻量级的数据结构，比如数组，我们知道，字符的种类是有限的，特别是这道题限制了全部都是小写字母，那么我们直接用大小为 26 的数组即可，这样压缩了空间。

前面我们是都统计完两个字符串之后，才进行对比，其实我们可以在统计第一个字符串的时候用加法，在统计第二个字符串的时候用减法，当出现负数的时候，那么就肯定不是重排字符串。

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1 == null && s2 == null) {
            return true;
        }
        if (s1 == null || s2 == null || s1.length() != s2.length()) {
            return false;
        }
        int[] counts = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            counts[s1.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s2.length(); i++) {
            if (counts[s2.charAt(i) - 'a'] == 0) {
                return false;
            }
            counts[s2.charAt(i) - 'a']--;
        }
        return true;
    }
}

空间复杂度其实是常数级，时间复杂度仍旧为 O(n)，只是减少了不必要的循环。