[leetcode]Interleaving String

처음에는 재 귀적 으로.빅 데이터 가 시간 을 초과 했다.나중에 인터넷 에서 봤 는데 동태 계획 이 었 어 요.결국 중복 서브 문제 가 있 습 니 다. 예 를 들 어 bbbaaa 는 bbaa 와 bbaa 가 일치 하면 첫 번 째 b 가 s1 을 선택 하 든 s2 를 선택 하 든 모두 baa 와 baa 같은 서브 문제 가 발생 합 니 다.
그러면 s1 + s2 = = s3 때문에 2 차원 배열 로 상 태 를 기록 하면 됩 니 다.상태 전이 방정식 은 상세 하 게 볼 수 있다. http://blog.unieagle.net/2012/09/29/leetcode%E9%A2%98%E7%9B%AE%EF%BC%9Ainterleaving-string%EF%BC%8C%E4%BA%8C%E7%BB%B4%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/
이것 은 마지막 으로 보 낸 동적 계획 버 전 입 니 다.

public class Solution {

    public boolean isInterleave(String s1, String s2, String s3) {

        // Start typing your Java solution below

        // DO NOT write main() function

        if (s1.length() + s2.length() != s3.length()) return false;

        boolean[][] status = new boolean[s1.length()+1][s2.length()+1];

        

        int len1 = s1.length();

        int len2 = s2.length();

        int len3 = s3.length();

        

        status[0][0] = true;

        for (int i = 1; i < s1.length()+1; i++) {

            status[i][0] = status[i-1][0] && s1.charAt(len1 - i) == s3.charAt(len3 - i);

        }

        

        for (int j = 1; j < s2.length()+1; j++) {

            status[0][j] = status[0][j-1] && s2.charAt(len2 - j) == s3.charAt(len3 - j);

        }

        

        for (int i = 1; i < s1.length()+1; i++) {

            for (int j = 1; j < s2.length()+1; j++) {

                status[i][j] = s3.charAt(len3 - i - j) == s1.charAt(len1 - i) && status[i-1][j] ||

                               s3.charAt(len3 - i - j) == s2.charAt(len2 - j) && status[i][j-1];

                

            }

        }

        

        return status[len1][len2];

    }

}

이것 은 빅 데이터 가 시간 을 초과 한 버 전 입 니 다. 저 는 그 배열 로 계 산 된 상 태 를 동적 으로 계획 하면 살 수 있 을 것 이 라 고 생각 합 니 다.

public class Solution {

    public boolean isInterleave(String s1, String s2, String s3) {

        // Start typing your Java solution below

        // DO NOT write main() function

        if (s1.length() + s2.length() != s3.length()) return false;

        return isInterleave(s1, s2, s3, 0, 0, 0);

        

    }

    

    public boolean isInterleave(String s1, String s2, String s3, int idx1, int idx2, int idx3) {

        if (idx3 == s3.length()) {

            if (idx1 == s1.length() && idx2 == s2.length()) return true;

            else return false;

        }

        

        boolean cond1 = idx1 < s1.length() && s1.charAt(idx1) == s3.charAt(idx3);

        boolean cond2 = idx2 < s2.length() && s2.charAt(idx2) == s3.charAt(idx3);

        if (cond1 && cond2) {

            return isInterleave(s1, s2, s3, idx1+1, idx2, idx3+1) ||

                    isInterleave(s1, s2, s3, idx1, idx2+1, idx3+1);

        }

        else if (cond1) {

            return isInterleave(s1, s2, s3, idx1+1, idx2, idx3+1);

        }

        else if (cond2) {

            return isInterleave(s1, s2, s3, idx1, idx2+1, idx3+1);

        }

        return false;

    }

    

}