Answer to Question #218177 in Python for Krish

Question

Write a program for interleave strings

Answer 1

def isInterleave(s1, s2, s3):
    len_s1, len_s2, len_s3 = len(s1), len(s2), len(s3)
    if len_s1 + len_s2 != len_s3:
        return False
    DP = [[False for i in range(len_s2 + 1)] for j in range(len_s1 + 1)]
    for i in range(len_s1 + 1):
        for j in range(len_s2 + 1):
            if i == 0 and j == 0:
                DP[i][j] = True
            elif i == 0:
                DP[i][j] = (DP[i][j-1] and s2[j-1] == s3[i+j-1])
            elif j == 0:
                DP[i][j] = (DP[i-1][j] and s1[i-1] == s3[i+j-1])
            else:
                DP[i][j] = (DP[i-1][j] and s1[i-1] == s3[i+j-1]) or (DP[i][j-1] and s2[j-1] == s3[i+j-1])
    return DP[len_s1][len_s2]


first_string, second_string, third_string = input('First string: '), input('Second string: '), input('Third string: ')
if isInterleave(first_string, second_string, third_string):
    print('Third string is an interleaving of first and second strings')
else:
    print("It is not possible to get third string by interleaving first and second strings")