LeetCode 솔루션 분류
[7/7] 97. Interleaving String
본문
Medium
5342317Add to ListShareGiven strings s1, s2, 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 + ... + snt = t1 + t2 + ... + tm|n - m| <= 1- The interleaving is
s1 + t1 + s2 + t2 + s3 + t3 + ...ort1 + 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 <= 1000 <= s3.length <= 200s1,s2, ands3consist 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]
