LeetCode #97 Interleaving String

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

LeetCode #97 Interleaving String

문제 풀이

dp로 풀어야 하나 고민했는데 dfs로도, bfs로도 풀리는 문제였다. 아직 문자열 다루는 심화문제에 약한 감이 있다. 별개로 이 문제는 생각할 점이 많은 좋은 문제기도 하다.

문제의 요지는 두 개의 스트링을 적당한 순서를 갖고 차례대로 추출하여 배열했을 때 주어진 스트링으로 만들 수 있는지 여부를 리턴해야 한다. 따라서 두 스트링의 길이가 주어진 스트링과 맞지 않으면 우선적으로 false를 리턴할 수 있다. 그리고 dfs건 bfs건 dp건 이전까지의 검증 좌표와 현재 탐색 좌표의 기준에 맞춰 탐색을 진행한 뒤 마지막 좌표의 결과를 리턴하면 된다. 성능은 bfs - dfs가 더 좋지만 공간복잡도는 dp가 더 좋았다.

• s1 길이 + s2길이 != s3 길이면 s1과 s2를 합쳐도 s3를 만들 수 없으므로 False
• dfs와 bfs로 구현할 경우 방문 대기열을 담을 stack이나 queue를 선언하여 set 자료형으로 방문체크를 한다.
• 시작점은 0, 0이고 시작점에 대해 다음 탐색지점을 담을지 결정해야 한다.
  • s1과 s2를 서로 구분하여 각각에 대해 검사를 진행한 뒤 대기열에 넣어야 한다.
  • (pos1 + 1, pos2)를 넣는 조건과 (pos1, pos2 + 1)를 넣는 조건 두 개가 필요하다.
  • 전자는 s1[pos1]과 s3[pos1 + pos2]의 검증이고 후자는 s2[pos2]과 s3[pos1 + pos2]의 검증이다.
  • 대기열에 좌표를 넣을 때 대기열에 넣는 좌표는 더 이상 탐색할 이유가 없으므로 visited set에 담는다.
• 대기열에서 좌표 추출 시 두 점의 좌표가 s3 길이와 동일하다면 True 반환
• 대기열에서 모든 좌표를 추출하여 탐색했음에도 True를 반환하지 못했다면 False 리턴

python 코드 - DFS

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        s1Len, s2Len, s3Len = len(s1), len(s2), len(s3)
        if s1Len + s2Len != s3Len:
            return False
        stack, visited = [(0, 0)], set((0, 0))
        while stack:
            pos1, pos2 = stack.pop()
            if pos1 + pos2 == s3Len:
                return True
            if pos1 < s1Len and s1[pos1] == s3[pos1 + pos2] and (pos1 + 1, pos2) not in visited:
                stack.append((pos1 + 1, pos2))
                visited.add((pos1 + 1, pos2))
            if pos2 < s2Len and s2[pos2] == s3[pos1 + pos2] and (pos1, pos2 + 1) not in visited:
                stack.append((pos1, pos2 + 1))
                visited.add((pos1, pos2 + 1))
        return False

python 코드 - BFS

from collections import deque
class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        s1Len, s2Len, s3Len = len(s1), len(s2), len(s3)
        if s1Len + s2Len != s3Len:
            return False
        queue, visited = deque([(0, 0)]), set()
        while queue:
            pos1, pos2 = queue.popleft()
            if pos1 + pos2 == s3Len:
                return True
            if pos1 < s1Len and s1[pos1] == s3[pos1 + pos2] and (pos1 + 1, pos2) not in visited:
                queue.append((pos1 + 1, pos2))
                visited.add((pos1 + 1, pos2))
            if pos2 < s2Len and s2[pos2] == s3[pos1 + pos2] and (pos1, pos2 + 1) not in visited:
                queue.append((pos1, pos2 + 1))
                visited.add((pos1, pos2 + 1))
        return False

python 코드 - DP

만약 dp인 경우에는 2차원 배열을 선언하여 두 개의 스트링에 대한 이전 좌표를 탐색하여 결정할 수 있다.

• [s1길이 + 1][s2길이 + 1]의 2차원 배열 생성(True로 초기화)
• s1, s2에 대해 다른 한 쪽을 고려하지 않고 s3의 좌표와 일치하는지 초기값 입력
  • 초기값을 세팅하는 이유는 본격적인 탐색 시 [i - 1][j] or [i][j - 1]좌표에 대해 탐색을 진행하는데 0좌표 기준으로 초기 값이 설정되지 않으면 유효하지 않은 조건임에도 True로 인지하기 때문이다. 마찬가지로 False로 초기화를 하더라도 유효한 조건임에도 False로 인지할 수 있기 때문에 어느쪽이건 초기화를 해야 한다.
• 이중 for문을 수행하되 [i][j]좌표의 값 입력은 [i - 1][j]가 유효하고 s1[i - 1] == s3[i - 1 + j]를 만족하거나 [i][j - 1]이 유효하고 s2[j - 1] == s3[i - 1 + j]를 만족해야 True로 간주한다. 그게 아니라면 False로 간주
• [s1길이][s2길이]좌표값의 결과를 리턴한다.

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        s1Len, s2Len, s3Len = len(s1), len(s2), len(s3)
        if s1Len + s2Len != s3Len:
            return False
        dp = [[True for _ in range(s2Len + 1)] for _ in range(s1Len = 1)]
        for i in range(1, s1Len + 1):
            dp[i][0] = dp[i - 1][0] and s1[i - 1] == s3[i - 1]
        for i in range(1, s2Len + 1):
            dp[0][i] = dp[0][i - 1] and s2[i - 1] == s3[i - 1]
        for i in range(1, s1Len + 1):
            for j in range(1, s2Len + 1):
                dp[i][j] = (dp[i - 1][j] and s1[i - 1] == s3[i - 1 + j]) or \
                (dp[i][j - 1] and s2[j - 1] == s3[i - 1 + j])
        return dp[s1Len][s2Len]