0

尝试实现一个函数以返回一个字符串是否是 s1、s2 的有效交错版本。遵循我的递归和记忆解决方案。

问题 - 记忆的解决方案没有探索所有可能的组合。第 k 个解决方案来自关于该问题的讨论帖子之一 - https://leetcode.com/problems/interleaving-string/

我正在尝试对第 k 个值检查的工作原理建立一个直观的理解。我的基本理解是，在探索多个分支时，第 i 个和第 j 个值出现一次，并且在没有真正探索其他组合的情况下被保存并重新检查。

真正尝试以更直观的方式理解解决方案。希望有更好的解释和/或它为什么起作用的数学原因。

递归解决方案：

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        
        if len(s1) + len(s2) < len(s3):
            return False
                
        memo = {}
        def helper(s1=s1, s2=s2, i=0, j=0, res=checker, combo='', memo=memo):
            if i == len(s1) and j == len(s2):
                res.add(''.join(combo))
                return
            if (i,j) in memo:
                return memo[(i,j)]
                
            if i < len(s1):
                memo[(i, j)] = True
                helper(s1, s2, i+1, j, res, combo + s1[i])
            if j < len(s2):
                memo[(i, j)] = True
                helper(s1, s2, i, j+1, res,  combo + s2[j])
        helper()
        return True if s3 in checker else False

备忘：

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        
        if len(s1) + len(s2) < len(s3):
            return False
       
        def helper(s1=s1, s2=s2, i=0, j=0,combo='', memo={}):
            if i == len(s1) and j == len(s2):
                return combo == s3
            if (i,j) in memo:
                return memo[(i,j)]                
            memo[(i,j)] = False            
            if i < len(s1):
                memo[(i,j)] |= helper(s1, s2, i+1, j, combo + s1[i], memo)                
            if j < len(s2):
                memo[(i,j)] |= helper(s1, s2, i, j+1, combo + s2[j], memo)            
            return memo[(i,j)]        
        return helper()

记忆并检查 s3 的第 k 个值：

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        elif s1 == '' and s2 == '':
            return s3 == ''
        elif s1 == '' or s2 == '':
            return s3 == s1 or s2

        def helper(s1=s1, s2=s2, i=0, j=0, k=0, s3=s3, path=[], mem={}):
            if i == len(s1) and j == len(s2):
                return "".join(path) == s3            
            if (i, j) in mem:
                return mem[(i, j)]
            mem[(i, j)] = False
            if i < len(s1) and s1[i] == s3[k]:
                mem[(i, j)] |= helper(s1, s2, i + 1, j, k + 1, s3, path + [s1[i]])
            if j < len(s2) and s2[j] == s3[k]:
                mem[(i, j)] |= helper(s1, s2, i, j + 1, k + 1, s3, path + [s2[j]])
            return mem[(i, j)]
        return helper()
4

0 回答 0