同源字符串检测

运行时间: 603 ms

内存: 114.8 MB

class Solution:
    def possiblyEquals(self, s1: str, s2: str) -> bool:
        m = len(s1)  # s1的长度
        n = len(s2)  # s2的长度
        memo = dict()  # 用于记忆化递归的字典

        # diff:跟踪两个字符串 s1和s2之间的潜在字符差异。
        # 具体来说，它表示在某个点上s1相对于s2的额外或缺少的字符数量。
        def helper(i, j, diff):
            # 如果两个字符串都遍历完成，并且差异为0，则返回True
            if i == m and j == n:
                return diff == 0
            # 如果当前状态已经计算过，则直接返回之前的结果
            if (i, j, diff) in memo:
                return memo[(i, j, diff)]

            # 如果s1的当前字符是数字
            if i < m and s1[i].isdigit():
                num = 0  # 用于记录数字的变量
                k = i
                # 计算数字的值
                while k < m and s1[k].isdigit():
                    num = num * 10 + int(s1[k])
                    k += 1
                    # 递归检查在考虑这个数字代表的重复次数后，两个字符串是否可能等价
                    if helper(k, j, diff + num):
                        return True
            # 如果s2的当前字符是数字:
            # why elif? especially in a scenario where multiple conditions are being checked sequentially.
            # It ensures that only one branch of the logic is executed for each iteration or recursion
            elif j < n and s2[j].isdigit():
                num = 0
                k = j
                # 计算数字的值
                while k < n and s2[k].isdigit():
                    num = num * 10 + int(s2[k])
                    k += 1
                    # 递归检查在考虑这个数字代表的重复次数后，两个字符串是否可能等价
                    if helper(i, k, diff- num):
                        return True
            # 如果当前没有字符重复的差异
            elif diff == 0:
                # 如果当前字符相同，则继续递归比较下一个字符
                if i < m and j < n and s1[i] == s2[j]:
                    if helper(i+1, j+1, diff):
                        return True
            # 如果s1需要更多字符来匹配s2
            elif diff > 0:
                if j < n:
                    if helper(i, j+1, diff - 1):
                        return True
            # 如果s2需要更多字符来匹配s1
            elif diff < 0:
                if i < m:
                    if helper(i+1, j, diff + 1):
                        return True

            # 如果当前状态不能使两个字符串等价，记录这个结果并返回False
            memo[(i, j, diff)] = False
            return False

        # 从两个字符串的起始位置开始递归检查
        return helper(0, 0, 0)
# s1 = "L3E"，
# s2 = "L1E2"
# 初始状态：diff = 0，因为两个字符串初始同步开始。

# 在s1中，数字是3，意味着有3个字符。
# 在s2中，紧接"L"的数字是1，意味着有1个字符，然后是"E"，然后是另外2个字符。
# 更新diff = 3 - 1 = 2。

# 由于s2中"E"之后还有2个字符，而在s1中，"E"之后没有更多的字符，这与我们之前计算的diff = 2相匹配，
# 表明在"E"之后，s1和s2可能有相同数量的额外字符。
# 根据diff的最终值和对字符串的分析，我们可以推断s1和s2可能表示同一个原始字符串，即"LXXXE"，
# 其中"X"表示任意字符。