给出两个长度相同的字符串,分别是 str1
和 str2
。请你帮忙判断字符串 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 <= == <= 10^4
-
str1
和str2
中都只会出现 小写英文字母
解题思路
我们首先观察一下这个问题,我们发现不可能出现一对多
这种映射情况。例如
a a b c c
c e ...
这是一个基准条件,接着我们还可以确定的是str1
和str2
中的字符种类数目要一直保持一致(也就是不能出现升维和降维的情况)。
我们需要判断str2
中包含多少个字母,如果包含了26
个的话,我们需要判断str1
和str2
是不是相等,如果二者不等的话直接返回False
,否则返回True
,为什么呢?例如
a b c ...
b c d ...
那么此时我们将a→b
b b c ...
b c d ...
那么就出现了str1
和str2
字符种类数目不一致,而当字符数目小于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
如有问题,希望大家指出!!!