字符串转化

Submission

运行时间: 32 ms

内存: 0.0 MB

class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        if str1 == str2:
            return True
        d = {}
        unique = set()
        for c1, c2 in zip(str1, str2):
            if c1 not in d:
                d[c1] = c2
                unique.add(c2)
            elif d[c1] != c2:
                return False
        return len(unique) < 26

Explain

此题解通过映射 str1 中的字符到 str2 中的字符来判断是否可以通过一系列转换将 str1 转换为 str2。首先，如果 str1 和 str2 完全相同，则无需任何转换，直接返回 True。接着，使用一个字典 d 来存储字符间的映射关系，以及一个集合 unique 来记录 str2 中已经被映射的字符。遍历 str1 和 str2 中的字符，若 str1 的字符未在字典中，将其添加进字典并记录对应的 str2 字符；若已存在映射且不符合当前 str2 字符，则无法完成转换，返回 False。最后，检查 unique 集合的长度是否小于 26，这是因为如果 str2 中有 26 个不同字符且都已被其他字符映射，则无法找到额外的字符来完成转换。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def canConvert(self, str1: str, str2: str) -> bool:
        if str1 == str2:
            return True  # 如果两个字符串相同，直接返回True
        d = {}  # 字典用于记录字符映射关系
        unique = set()  # 集合用于记录str2中已映射的字符
        for c1, c2 in zip(str1, str2):
            if c1 not in d:
                d[c1] = c2  # 建立映射关系
                unique.add(c2)  # 记录该字符已被映射
            elif d[c1] != c2:
                return False  # 如果存在矛盾的映射关系，则返回False
        return len(unique) < 26  # 检查是否有足够的字符可用于映射

Explore

在检查`len(unique) < 26`时，这个条件是关键的，因为它确保在所有26个英文字母都已经被用作映射目标的情况下，仍有至少一个字母可用于完成任何未完成的映射。如果`unique`的长度达到26，意味着每一个英文字母已经被str2中的某个字符占用，这时如果str1中还有未映射到str2的字符存在，就不可能找到新的字符来完成映射，因此无法实现有效的一对一映射。

如果`c1`已经在映射字典`d`中存在，但原映射的目标字符与当前的`c2`不一致，这种情况下可能会导致问题。例如，如果str1中的某个字符在不同位置需要映射到str2中的不同字符，这将造成矛盾。如果没有适当的检查和处理这种矛盾，算法可能会错误地认为映射是可行的。

矛盾的映射关系指的是同一个字符在str1中被映射到str2中的多个不同字符。例如，假设str1为 'aba' 而str2为 'xyz'，按照映射关系，第一个字符'a'应该映射到'x'，但在第三个字符位置，'a'又需要映射到'z'，这就形成了矛盾，因为一个字符不能同时映射到两个不同的字符。

如果`str1`比`str2`更长，这种情况下算法是无效的。因为题解中的算法基于假设`str1`和`str2`长度相同，通过zip函数同时遍历两个字符串。如果`str1`更长，那么`str2`中将没有足够的字符来映射`str1`的额外字符，因此不可能实现完全的字符映射。