跳转至

面试题 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
12
13
14
15
16
17
18
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) {
            return false;
        }
        int cnt[26]{};
        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
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 {
        if cnt[c-'a']--; cnt[c-'a'] < 0 {
            return false
        }
    }
    return true
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function CheckPermutation(s1: string, s2: string): boolean {
    if (s1.length !== s2.length) {
        return false;
    }
    const cnt: Record<string, number> = {};
    for (const c of s1) {
        cnt[c] = (cnt[c] || 0) + 1;
    }
    for (const c of s2) {
        if (!cnt[c]) {
            return false;
        }
        cnt[c]--;
    }
    return true;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
impl Solution {
    pub fn check_permutation(s1: String, s2: String) -> bool {
        if s1.len() != s2.len() {
            return false;
        }

        let mut cnt = vec![0; 26];
        for c in s1.chars() {
            cnt[(c as usize - 'a' as usize)] += 1;
        }

        for c in s2.chars() {
            let index = c as usize - 'a' as usize;
            if cnt[index] == 0 {
                return false;
            }
            cnt[index] -= 1;
        }

        true
    }
}

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

        var cnt = [Int](repeating: 0, count: 26)

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

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

        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) {
        ranges::sort(s1);
        ranges::sort(s2);
        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
    }
}

1
2
3
4
5
6
7
8
/**
 * @param {string} s1
 * @param {string} s2
 * @return {boolean}
 */
var CheckPermutation = function (s1, s2) {
    return [...s1].sort().join('') === [...s2].sort().join('');
};

1
2
3
4
5
6
7
class Solution {
    func CheckPermutation(_ s1: String, _ s2: String) -> Bool {
        let s1 = s1.sorted()
        let s2 = s2.sorted()
        return s1 == s2
    }
}

评论