以 pythonic 方式检查交织字符串

Question

我在检查交织字符串时遇到了问题。所以，我有 3 个字符串，我需要检查是否可以通过交织前两个字符串来形成第三个字符串。

为了简化，交织字符串意味着通过交替字母来合并它们，没有任何特定模式。

例如："abc" 和 "123" 是两个字符串，可能的交织可以是 "abc123" 或 "a1b2c3" 或 "ab1c23" 等将它们混合在一起而没有任何模式但遵循顺序。

另一个例子，对于错误的情况：

str1 = "aabcc", 
str2 = "dbbca", 
str3 = "aadbbbaccc"  # This is false case, where str3 is not interweaving from str1 and str2

我试过的：

我尝试了以下适合我的解决方案。如果字符串 c 是字符串 a 和 b 的交织，则返回 True 否则返回 False

def weavingstring(a,b,c):
    for i in c:
        if len(a)>0:
            if i == a[0]:
                a=a[1:]
        if len(b)>0:
            if i == b[0]:
                b=b[1:]
    if len(a) > 0 or len(b) > 0:
        return False
    return True
            

print(weavingstring("abc", "def", "abcdef"))  # True here
print(weavingstring("aabcc", "dbbca", "aadbbbaccc"))  # False here

我想要什么

我有正常的解决方案，我想知道是否有使用 list comprehension、map、filter、reduce 或lambda functions等

Answer 1

一个简单的解决方案是使用正则表达式。

import re
def iswoven(first, second, test):
    return all((re.search(r'.*'.join(x), test) for x in (first, second)))


>>> iswoven('abc', '123', 'a1b2c23')
True
>>> iswoven('abc', '123', 'a1b223')
False

这将检查测试字符串是否匹配 'a.*b.*c' 和 '1.*2.*3' 以及 return 结果。

根据字符串的长度，这可能最终会尝试匹配一些非常复杂的正则表达式，所以买家要当心。

Answer 2

一种使用 lru_cache 和 lambda 来加快速度的方法向上：

from functools import lru_cache
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        return (memo:=lru_cache()
            ( lambda i=0, j=0, k=0:
                (i, j, k) == (len(s1), len(s2), len(s3))
                or ( i < len(s1) and k < len(s3) and s1[i] == s3[k] and memo( i+1, j, k+1 ) )
                or ( j < len(s2) and k < len(s3) and s2[j] == s3[k] and memo( i, j+1, k+1 ) ) )
        )()

Answer 3

我可以对一个简单的递归解决方案感兴趣吗？

def weaving(a: str, b: str, res: str) -> bool:
    if not a: return b == res
    if not b: return a == res
    if not res: return False
    if res[0] == a[0]:
        return weaving(a[1:], b, res[1:])
    elif res[0] == b[0]:
        return weaving(a, b[1:], res[1:])
    else:
        return False

以 pythonic 方式检查交织字符串

Checking interweaving strings in pythonic way

python

lambda

mapreduce

list-comprehension

python-3.x