【程序员面试金典】01.02. 判定是否互为字符重排

判定是否互为字符重排

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

输入: s1 = “abc”, s2 = “bca”
输出: true

示例 2：

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

说明：

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

题目解法

  假定变位词区分大小写，且考虑空白字符，即“god”不是“ dog”的变位词。首先请注意不同长度的字符串不可能互为重排字符串。解决这个问题的两种简单的方法，都采用了上述优化方法。

解法1：排序字符串

  若两个字符串互为重排字符串，那么它们拥有同一组字符，只不过顺序不同。因此，对字符串排序，组成这两个重排字符串的字符就会有相同的顺序。我们只需要比较排序后的字符串。此算法效率虽算不上最优，但贵在清晰简单易懂。

import java.util.Arrays;

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) { // 互为字符重排必须长度相同
            return false;
        }
        return sort(s1).equals(sort(s2));
    }
    
    /* 字符串排序 */
    private String sort(String s) {
        char[] content = s.toCharArray();
        Arrays.sort(content);
        return new String(content);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解法2：检查两个字符串的字符数是否相同

  可以充分利用变位词的定义：组成两个单词的字符数相同，来实现这个算法。创建一个类似散列表的数组，将其每个字符映射到其字符出现的次数。增加第一个字符串，然后减少第二个字符串，如果两者互为重排，则该数组最终将为0。
  若值为负数(一旦为负，则值将永为负，不会为非0)，就提前终止。原因在于，字符串长度相同，每个字符增加的次数与减少的次数也相同，若出现负值，必然有字符在s1和s2中出现的次数不一致，s1和s2不会互为重排字符串。

public class Solution2 {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) { // 互为字符重排必须长度相同
            return false;
        }
        int[] characters = new int[128]; // 假设为ASCII字符
        for (int i = 0; i < s1.length(); i++) { // 统计s1中字符出现的次数
            characters[s1.charAt(i) - 'a']++;
        }
        
        for (int i = 0; i < s2.length(); i++) { // 减去s2字符出现的次数
            // 因字符串长度相同，若某个字符出现次数为负数，则这个字符在s2出现的次数必然和s1不一致，s1和s2不互为字符重排，直接结束
            if (--characters[s2.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

参考文献：

[1] 盖尔.拉克曼.麦克道尔.程序员面试金典（第6版）[M].北京：人民邮电出版社，2019.9：157-158
[2] leetcode.面试题 01.02. 判定是否互为字符重排