Участник:Alexryabov/TaskInterleavingString

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/interleaving-string/

 
class Solution(object):
    def isInterleave(self, s1, s2, s3):
        a = len(s1)
        b = len(s2)
 
        arr = [[0] * (b + 1) for i in range(a + 1)]
 
        if (a + b) != len(s3):
            return False
 
        arr[0][0] = 1
 
        for i in range(1, a + 1):
            if s3[i - 1] == s1[i - 1]:
                arr[i][0] = arr[i - 1][0]
        for j in range(1, b + 1):
            if s3[j - 1] == s2[j - 1]:
                arr[0][j] = arr[0][j - 1]
 
 
        for i in range(1, a + 1):
            for j in range(1, b + 1):
                if s3[i + j - 1] == s1[i - 1]:
                    arr[i][j] = (arr[i][j] or arr[i - 1][j])
                if s3[i + j - 1] == s2[j - 1]:
                    arr[i][j] = (arr[i][j] or arr[i][j - 1])
 
        return arr[-1][-1]