Leetcode 1153:字符串转化(超详细的解法!!!)

时间:2025-02-14 08:09:53

给出两个长度相同的字符串,分别是 str1str2。请你帮忙判断字符串 str1 能不能在 零次多次 转化后变成字符串 str2

每一次转化时,将会一次性将 str1 中出现的 所有 相同字母变成其他 任何 小写英文字母(见示例)。

只有在字符串 str1 能够通过上述方式顺利转化为字符串 str2 时才能返回 True,否则返回 False

示例 1:

输入:str1 = "aabcc", str2 = "ccdee"
输出:true
解释:将 'c' 变成 'e',然后把 'b' 变成 'd',接着再把 'a' 变成 'c'。注意,转化的顺序也很重要。

示例 2:

输入:str1 = "leetcode", str2 = "codeleet"
输出:false
解释:我们没有办法能够把 str1 转化为 str2。

提示:

  1. 1 <= == <= 10^4
  2. str1str2 中都只会出现 小写英文字母

解题思路

我们首先观察一下这个问题,我们发现不可能出现一对多这种映射情况。例如

a a b c c
c e ...

这是一个基准条件,接着我们还可以确定的是str1str2中的字符种类数目要一直保持一致(也就是不能出现升维和降维的情况)。

我们需要判断str2中包含多少个字母,如果包含了26个的话,我们需要判断str1str2是不是相等,如果二者不等的话直接返回False,否则返回True,为什么呢?例如

a b c ...
b c d ...

那么此时我们将a→b

b b c ...
b c d ...

那么就出现了str1str2字符种类数目不一致,而当字符数目小于26的时候就可以满足条件。所以下面的代码就很显然了

class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        n, m = len(str1), len(set(str2))
        if m == 26:
            return str1 == str2
        
        d = {}
        for i, c in enumerate(str1):
            if c in d:
                if d[c] != str2[i]:
                    return False
            else:
                d[c] = str2[i]
        return True

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!