leetcode面试题 01.02(判定是否互为字符重排)–Java语言实现

求：

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

示例 1：

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

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

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

题目链接： https://leetcode-cn.com/problems/check-permutation-lcci/submissions/

解：

1、排序

根据题目要求，如果s2是s1的字符重排，则s2与s1的长度一定相等，且s2与s1中包含的字符的种类应该完全一致，每一种字符出现的次数也应该完全一致。

那么如果对s1和s2按照字符的字典顺序进行排序，s1和s2一定是2个相等的字符串。

时间复杂度：O(NlogN)

空间复杂度：O(N)

public boolean CheckPermutation(String s1, String s2) {
    char[] chars1 = s1.toCharArray();
    char[] chars2 = s2.toCharArray();
    Arrays.sort(chars1);
    Arrays.sort(chars2);
    return String.valueOf(chars1).equals(String.valueOf(chars2));
}

2、数组计数

与解法1类似，但比解法1要好。这里我们使用一个数组count[]来存储每一种类型的字符出现的次数。因为题目没有说明字符串的组成，所以这里给count分配的空间是256。然后我们先遍历s1，遍历完成s1后，count记录了s1中每一种字符出现的次数。然后我们再遍历s2，每遍历s2中的一个字符，就将count对应位置减去1。如果我们发现某个元素对应的count计数在减去1后小于0，说明s2中出现了s1中没有出现过的元素，返回false。否则返回true。

注意：这里第一句先判断s1和s2长度相等是必须的。因为如果s1和s2长度相等，而s1与s2的元素出现的次数不同，那么一定是s1有一些元素s2没有，同时s2有一些元素s1没有，for循环一定会返回false。但是如果没有先判断相等，则可能s1的长度很长，s2很短，这时候for循环不会返回false，会出现错误判断。

时间复杂度：O(N)

空间复杂度：O(N)

public boolean CheckPermutation(String s1, String s2) {
    if (s1.length() != s2.length()) return false;
    int count[] = new int[256];
    for (int i = 0; i < s1.length(); i++) {
        count[s1.charAt(i)]++;
    }
    for (int i = 0; i < s2.length(); i++) {
        if (--count[s2.charAt(i)] < 0) return false;
    }
    return true;
}