<Medium> Interleaving String (LeetCode : C#)

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

📕 문제 설명

문자열 s1, s2, s3가 주어질 때 s3가 s1과 s2를 끼워 넣어 만들어 진 것이 맞는지 반환

• interleaving
  두 문자열 s, t가 있을 때 s와 t를 각각 n과 m개의 하위 문자열로 나눈다.
  s = s1 + s2 + .. + sn
  t = t1 + t2 + .. + tm
  이때 interleaving은 s1 + t1 + s2 + t2 + s3 + t3.. 형태이거나 t1 + s1 + t2 +s2 +t3 + s3.. 형태이다.

• Input
  문자열 s1, s2, s3
• Output
  s3가 s1과 s2의 interleaving 인지 반환 (bool)

예제

풀이

memoization 이용해서 풀었다. 최종적으로 s3 만들 수 있냐를 보는데 s1과 s2 하위 문자열 더할 때 시작 순서 상관 없어서 if문 두 케이스로 나누고 진행

memo는 i,j에 대해 bool 결과를 가질 수 있는 경우만 visited했다고 정의하기 위해 nullable로 정의

public class Solution {
    public bool IsInterleave(string s1, string s2, string s3) {
        if (s1.Length + s2.Length != s3.Length) return false;
        if (s3.Length == 0) return true;
        
        bool?[,] memo = new bool?[s1.Length + 1, s2.Length + 1];

        return dfs(0, 0);

        bool dfs(int i, int j) 
        {
            if (i + j == s3.Length) return true;
            if (memo[i, j].HasValue) return memo[i, j].Value;
            bool res = false;
            // s3와 현재 보고있는 인덱스가 일치하면 문자열에 대해 포인터 옮기기 (s1, s2 각각)
            // 예제에서는 aa / dbbc/ bc/ a / c 이렇게 끊기는 것을 볼 수 있다 (위에 if, 아래 if, 위에 if 이런식으로 걸림)
            if (i < s1.Length && s1[i] == s3[i + j]) res |= dfs(i + 1, j); // s1 먼저 하는 케이스
            if (j < s2.Length && s2[j] == s3[i + j]) res |= dfs(i, j + 1); // s2 먼저 하는 케이스
            memo[i, j] = res;
            return res;
        }
    }
}

결과