跳转至

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

题目描述

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

示例 1：

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

示例 2：

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

说明：

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

解法

方法一：数组或哈希表

我们先判断两个字符串的长度是否相等，若不相等则直接返回 false。

然后用一个数组或哈希表统计字符串 $s1$ 中字符出现的次数。

接着遍历另一个字符串 $s2$，每遍历到一个字符，就将该字符对应的次数减一，如果减一后的次数小于 $0$，则说明两个字符串中字符出现的次数不同，直接返回 false。

最后遍历完字符串 $s2$，返回 true。

注意：本题测试用例所有字符串仅包含小写字母，因此我们可以直接开一个长度为 $26$ 的数组来计数。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串的长度，而 $C$ 为字符集的大小，本题 $C=26$。

1
2
3
class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        return Counter(s1) == Counter(s2)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if (s1.length() != s2.length()) {
            return false;
        }
        int[] cnt = new int[26];
        for (char c : s1.toCharArray()) {
            ++cnt[c - 'a'];
        }
        for (char c : s2.toCharArray()) {
            if (--cnt[c - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        int cnt[26] = {0};
        for (char& c : s1) ++cnt[c - 'a'];
        for (char& c : s2)
            if (--cnt[c - 'a'] < 0) return false;
        return true;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func CheckPermutation(s1 string, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    cnt := make([]int, 26)
    for _, c := range s1 {
        cnt[c-'a']++
    }
    for _, c := range s2 {
        cnt[c-'a']--
        if cnt[c-'a'] < 0 {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
function CheckPermutation(s1: string, s2: string): boolean {
    const n = s1.length;
    const m = s2.length;
    if (n !== m) {
        return false;
    }
    const map = new Map<string, number>();
    for (let i = 0; i < n; i++) {
        map.set(s1[i], (map.get(s1[i]) ?? 0) + 1);
        map.set(s2[i], (map.get(s2[i]) ?? 0) - 1);
    }
    for (const v of map.values()) {
        if (v !== 0) {
            return false;
        }
    }
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
use std::collections::HashMap;
impl Solution {
    pub fn check_permutation(s1: String, s2: String) -> bool {
        let n = s1.len();
        let m = s2.len();
        if n != m {
            return false;
        }
        let s1 = s1.as_bytes();
        let s2 = s2.as_bytes();
        let mut map = HashMap::new();
        for i in 0..n {
            *map.entry(s1[i]).or_insert(0) += 1;
            *map.entry(s2[i]).or_insert(0) -= 1;
        }
        map.values().all(|i| *i == 0)
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var CheckPermutation = function (s1, s2) {
    if (s1.length != s2.length) {
        return false;
    }
    const cnt = new Array(26).fill(0);
    for (let i = 0; i < s1.length; ++i) {
        const j = s1.codePointAt(i) - 'a'.codePointAt(0);
        ++cnt[j];
    }
    for (let i = 0; i < s2.length; ++i) {
        const j = s2.codePointAt(i) - 'a'.codePointAt(0);
        if (--cnt[j] < 0) {
            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
24
class Solution {
    func CheckPermutation(_ s1: String, _ s2: String) -> Bool {
        if s1.count != s2.count {
            return false
        }

        var cnt = Array(repeating: 0, count: 26)

        for char in s1 {
            let index = Int(char.asciiValue! - Character("a").asciiValue!)
            cnt[index] += 1
        }

        for char in s2 {
            let index = Int(char.asciiValue! - Character("a").asciiValue!)
            cnt[index] -= 1
            if cnt[index] < 0 {
                return false
            }
        }

        return true
    }
}

方法二：排序

我们也按照字典序对两个字符串进行排序，然后比较两个字符串是否相等。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为字符串的长度。

1
2
3
class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        return sorted(s1) == sorted(s2)

1
2
3
4
5
6
7
8
9
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        Arrays.sort(cs1);
        Arrays.sort(cs2);
        return Arrays.equals(cs1, cs2);
    }
}

1
2
3
4
5
6
7
8
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        sort(s1.begin(), s1.end());
        sort(s2.begin(), s2.end());
        return s1 == s2;
    }
};

1
2
3
4
5
6
func CheckPermutation(s1 string, s2 string) bool {
    cs1, cs2 := []byte(s1), []byte(s2)
    sort.Slice(cs1, func(i, j int) bool { return cs1[i] < cs1[j] })
    sort.Slice(cs2, func(i, j int) bool { return cs2[i] < cs2[j] })
    return string(cs1) == string(cs2)
}

1
2
3
function CheckPermutation(s1: string, s2: string): boolean {
    return [...s1].sort().join('') === [...s2].sort().join('');
}

1
2
3
4
5
6
7
8
9
impl Solution {
    pub fn check_permutation(s1: String, s2: String) -> bool {
        let mut s1: Vec<char> = s1.chars().collect();
        let mut s2: Vec<char> = s2.chars().collect();
        s1.sort();
        s2.sort();
        s1 == s2
    }
}

评论