【2022-09-27每日一题】面试题 01.02. 判定是否互为字符重排[Easy]

2022-09-27每日一题：面试题 01.02. 判定是否互为字符重排

难度：Easy

标签：哈希表 、 字符串 、 排序

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

示例 1：

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

示例 2：

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

说明：

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

方法一：排序

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func CheckPermutation(s1 string, s2 string) bool {
    b1, b2 := []byte(s1), []byte(s2)
    sort.Slice(b1, func(i, j int) bool {return b1[i] < b1[j]})
    sort.Slice(b2, func(i, j int) bool {return b2[i] < b2[j]})
    // return reflect.DeepEqual(b1, b2)
    return string(b1) == string(b2)
}

复杂度分析

• 时间复杂度：O(nlogn)。
• 空间复杂度：O(logn)。

方法二：哈希表

func CheckPermutation(s1 string, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }
    mp := map[byte]int{}
    for i := 0; i < len(s1); i++ {
        mp[s1[i]]++
        mp[s2[i]]--
    }
    for _, v := range mp {
        if v != 0 {
            return false
        }
    }
	return true
}


// 官方
func CheckPermutation(s1 string, s2 string) bool {
    var c1, c2 [128]int
    for _, ch := range s1 {
        c1[ch]++
    }
    for _, ch := range s2 {
        c2[ch]++
    }
    return c1 == c2
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为 s1的长度。

• 空间复杂度：O(S)，其中 S 为字符集大小，此处 S=128。

LeetCode题库地址

• https://leetcode.cn/problems/check-permutation-lcci