[LeetCode] Interleaving String 문제풀이 보고서

[제목]
Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example, Given: s1 =  "aabcc" , s2 =  "dbbca" ,
When s3 =  "aadbbcbcac" , return true. When s3 =  "aadbbbaccc" , return false. [해석]
제목: 두 개의 문자열 s1과 s2가 있습니다. 이 두 문자열 중 하나에서 한 글자 (앞에서 뒤로) 를 꺼낼 때마다 두 문자열을 모두 꺼냅니다. 이렇게 하면 많은 새로운 문자열을 구성할 수 있습니다. s3이 새로 구성된 문자열 중 하나에 속하는지 물어보십시오.
폭력 귀속법은 가장 직접적인 생각이지만 시간을 초과할 수 있다.
동적 기획법의 가장 관건적인 것은 동규 방정식을 찾는 것이다. 다시 말하면 어떻게 2차원수 그룹을 구성하는지, 그리고 2차원수 그룹 dp[i][j]가 어떤 의미를 의미하는지 말한다.
다음 코드에서 dp[i][j]는 s2의 전 i 문자와 s1의 전 j 문자가 s3의 전 i+j 문자와 일치하는지 여부를 나타낸다.
dp[0][0]=0을 초기화하고 dp[0][j]는 s2가 0을 얻는 것을 의미한다. 즉, s1의 전 j 문자가 s3의 전 j 문자와 일치하는지 여부를 나타낸다.dp[i][0]는 s1이 0개, 즉 s2의 전 i 문자를 얻었는지, s3의 전 i 문자와 일치하는지 여부를 나타낸다.
정규 방정식: dp[i] [j] = dp[i-1] [j] [j] & s2 [i-1] = s3 [i+ j- 1] = s3 [i+ 1] |||| dp[i] = s3 [i- 1] = s3 [i+j-1] = = s3 [i+ j-1 문자와 s3 [i+ 1] | = s3 [i+ j-1 1] = = s3 [i+ 1] = = s3 [i+ j-1 문자와 s3 [i+ 1] = = = = = s3 [i+ j-1 = = = = = = = = = = s3 문자와 s3 [i+ j-1 문자와 s2 문자와 s2 문자와 s3 문자와 s3 문자와 s3 문자와 s3 문자와 s3 문자와 s3 j-1 문자 일치,또한 s1의 j 문자는 s3의 i+j 문자와 같으면 s2의 전 i 문자와 s1의 전 j 문자는 s3의 전 i+j-1 문자와 일치할 수 있습니까?
[Java 코드]

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;
        
        boolean[][] dp = new boolean[s2.length() + 1][s1.length() + 1];
        dp[0][0] = true;
        for (int j = 1; j <= s1.length(); j++) {
            dp[0][j] = dp[0][j - 1] && (s1.charAt(j - 1) == s3.charAt(j - 1));
        }
        for (int i = 1; i <= s2.length(); i++) {
            dp[i][0] = dp[i - 1][0] && (s2.charAt(i - 1) == s3.charAt(i - 1));
        }
        
        for (int i = 1; i <= s2.length(); i++) {
            for ( int j = 1; j <= s1.length(); j++) {
                dp[i][j] = dp[i - 1][j] && (s2.charAt(i - 1) == s3.charAt(i + j - 1))
                        || dp[i][j - 1] && (s1.charAt(j - 1) == s3.charAt(i + j - 1));
            }
        }
        
        return dp[s2.length()][s1.length()];
    }
}

참고 자료https://leetcode.com/discuss/22726/dp-solution-in-java