엔지니어 게시판
LeetCode 솔루션 분류

[7/7] 97. Interleaving String

컨텐츠 정보

본문

Medium
5342317Add to ListShare

Given strings s1s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where they are divided into non-empty substrings such that:

  • s = s1 + s2 + ... + sn
  • t = t1 + t2 + ... + tm
  • |n - m| <= 1
  • The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.

 

Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true

 

Constraints:

  • 0 <= s1.length, s2.length <= 100
  • 0 <= s3.length <= 200
  • s1s2, and s3 consist of lowercase English letters.

 

Follow up: Could you solve it using only O(s2.length) additional memory space?

관련자료

댓글 1

학부유학생님의 댓글

  • 익명
  • 작성일
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if not len(s1+s2) == len(s3): return False
        
        dp = [[False]*(len(s2)+1) for _ in range(len(s1)+1)]
        dp[len(s1)][len(s2)] = True
        
        for i in range(len(s1),-1,-1):
            for j in range(len(s2), -1, -1):
                if i < len(s1) and dp[i+1][j] and s3[i+j] == s1[i]:
                    dp[i][j] = True
                if j < len(s2) and dp[i][j+1] and s3[i+j] == s2[j]:
                    dp[i][j] = True
        
        return dp[0][0]
        
        
        
        
전체 94 / 2 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0