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

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例 1：

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

示例 2：

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

说明：

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

题目思考

1. 互为字符重排的充要条件是什么?

解决方案

思路

• 要想使得一个字符串重新排列后能变成另一个字符串, 首先两者长度肯定得相等, 其次它们的字符个数需要完全一样, 而字符位置无所谓
• 所以我们先判断两者长度; 然后用一个计数字典, 先统计第一个字符串的各个字符个数, 然后再遍历第二个字符串, 将对应字符的计数-1, 如果小于 0 则返回 false, 如果正常遍历完毕则返回 true
• 正常遍历完毕可以直接返回 true 的原因: 在长度相等的前提下, 如果没有计数小于 0 的情况, 假设结束时有计数大于 0 的字符, 那么减少的计数总数一定小于增加的计数总数, 这和两个字符串长度相等矛盾

复杂度

• 时间复杂度 O(N): 需要遍历每个字符串一遍
• 空间复杂度 O(N): 需要一个计数字典

代码

from collections import defaultdict


class Solution:
    def CheckPermutation(self, s1: str, s2: str) -> bool:
        # 先判断长度
        # 再使用一个计数字典
        if len(s1) != len(s2):
            return False
        d = defaultdict(int)
        for c in s1:
            d[c] += 1
        for c in s2:
            d[c] -= 1
            if d[c] < 0:
                return False
        return True

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊