Checking interweaving strings in pythonic way

user_7400128 0
Viewed 86

I have a problem for checking the interweaving strings. So, I have 3 strings and I need to check whether the third string can be formed by interweaving the first two strings.

To simplify, interweaving strings means to merge them by alternating their letters without any specific pattern.

For example: "abc" and "123" are two strings and possible interweaving can be "abc123" or "a1b2c3" or "ab1c23" etc mixing them without any pattern but following order sequence.

another example, for false case:

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

what i have tried:

I have tried below solution which is working for me. returning True if string c is interweaving of string a and b else returning 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

What i want

I have the normal solution, I wanted to know if there is any pythonic way of doing this by using list comprehension, map, filter, reduce or lambda functions etc.

mapreduce list-comprehension python-3.x lambda python
3 Answers

One approach of using the lru_cache with lambda to speed things up:

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 ) ) )
        )()
user_107607680

May I interest you in a simple recursive solution?

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
user_111172100

A simple solution would be to use regexes.

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

This will check that the test string matches both 'a.*b.*c' and '1.*2.*3' and return the result.

Depending on the length of your strings, this could end up trying to match on some pretty hairy regexes, so buyer beware.

user_76378700
Related