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

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

示例 1：

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/check-permutation-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

 // 1,分别对两个字符串char数组
    // 2,排序两个数组
    // 3,循环比较两个数组的每一位，不一致return false
    // 4,比较到最后，都相同。 return true
    public boolean CheckPermutation(String s1, String s2) {

        if (s1 == null && s2 == null) return true;
        if (s1 == null || s2 == null) return false;
        if (s1.length() != s2.length()) return false;

        char[]c1 = s1.toCharArray();
        char[]c2 = s2.toCharArray();

        Arrays.sort(c1);
        Arrays.sort(c2);

        for (int i = 0; i < c1.length; i++) {
            if (c1[i] != c2[i]) return false;
        }
        return true;
    }

思路二：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// 用数组存储，字符串中每个字符的出现次数。
    // 遍历字符串
    // s1中存在的字符， 数组对应位置 + 1
    // s2中存在的字符， 数组对应位置 - 1
    // 最后，遍历数组，有不为0的位置，则不是重排
    // 所有位置都为0， 则true
    public boolean CheckPermutation1(String s1, String s2){
        if (s1 == null && s2 == null) return true;
        if (s1 == null || s2 == null) return false;
        if (s1.length() != s2.length()) return false;

        int[] tmp = new int[256];
        for (int i = 0; i < s1.length(); i++) {
            tmp[s1.charAt(i)] ++;
            tmp[s2.charAt(i)] --;
        }

        for (int i = 0; i < 256; i++) {
            if (tmp[i] != 0) return false;
        }

        return true;
    }