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

Posted on | In
Words count in article: 531 | Reading time ≈ 2

题目

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

示例 1:

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

示例 2:

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

提示:

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

解法

解法一：

借助HashMap。

首先两者长度必须相等。

遍历s1，每个字符存入HashMap。遍历s2，判断是否每个字符都在s1里面出现,并且出现的次数相同。

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()) {
            return false;
        }

        Map<Character, Integer> map = new HashMap<>();
        for (char c : s1.toCharArray()) {
            if (map.containsKey(c)) {
                map.replace(c, map.get(c) + 1); 
            } else {
                map.put(c, 1);
            }
        }

        for (char c : s2.toCharArray()) {
            if (map.containsKey(c)) {
                int count = map.get(c);
                if (1 == count) {
                    map.remove(c);
                } else {
                    map.replace(c, map.get(c) - 1);
                }
            } else {
                return false;
            }
        }
        return true;
    }

解法二：

将s1和s2转为字符数组c1和c2，对其两个字符数组排序，遍历，挨个比较，不一致返回false

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean CheckPermutation(String s1, String s2) {
        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;
    }

解法三：

异或运算.

如果两个字符数组刚好是对方的字符重排，那么它们的异或结果一定为0.

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean CheckPermutation(String s1, String s2) {
        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;
    }

解法四：

计数排序。

计算每个字符出现的次数，如果s2中出现的次数不一致，则返回false

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()){
            return false;
        }

        int[] temp = new int[256];
        for(int i=0;i<s1.length();i++){
            temp[s1.charAt(i)]++;
        }
        for(int i=0;i<s2.length();i++){
            if(temp[s2.charAt(i)] == 0){
                return false;
            }
            temp[s2.charAt(i)]--;
        }
        return true;
    }
}
0%