[LeetCode/Medium] 97. Interleaving String (JAVA)

문제

---

DFS 풀이

그냥 DFS로 풀었더니 시간 초과가 났다!

코드

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;

        return dfs(0, 0, 0, s1, s2, s3);
    }
    
    private boolean dfs(int i1, int i2, int i3, String s1, String s2, String s3) {
        if (i3 == s3.length()) return true;
        
        boolean result = false;
        if (i1 < s1.length() && s1.charAt(i1) == s3.charAt(i3))
            result |= dfs(i1+1, i2, i3+1, s1, s2, s3);
        
        if (i2 < s2.length() && s2.charAt(i2) == s3.charAt(i3))
            result |= dfs(i1, i2+1, i3+1, s1, s2, s3);
        
        return result;
    }
}

---

DFS+DP 풀이

런타임 단축을 위해 invalid 배열을 사용해서 먼저 유효성 검사를 하게 했더니 통과했다! 근데 런타임이 2324msㅋㅋㅋㅋㅋㅋㅋㅋ라서.. 더 나은 방법을 생각해봤따...

코드

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;

        return dfs(0, 0, 0, s1.toCharArray(), s2.toCharArray(), s3.toCharArray(), new boolean[s1.length()+1][s2.length()+1]);
    }
    
    private boolean dfs(int i1, int i2, int i3, char[] s1, char[] s2, char[] s3, boolean[][] invalid) {
        if (i3 == s3.length) return true;
        
        if (invalid[i1][i2]) return false;
        
        boolean valid = false;
        if (i1 < s1.length && s1[i1] == s3[i3])
            valid |= dfs(i1+1, i2, i3+1, s1, s2, s3, invalid);
        
        if (i2 < s2.length && s2[i2] == s3[i3])
            valid |= dfs(i1, i2+1, i3+1, s1, s2, s3, invalid);
        
        if (!valid) invalid[i1][i2] = true;
        
        return valid;
    }
}

---

DP 풀이

재귀를 없애고 반복문으로 isValid 배열을 채워나가는 방식으로 바꿨더니 런타임 시간이 2ms로 단축됐다 ㅎㅎ;
인덱싱만 주의하면 점화식은 쉽게 떠올릴 수 있다.

풀이

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) return false;

        char[] c1 = s1.toCharArray();
        char[] c2 = s2.toCharArray();
        char[] c3 = s3.toCharArray();
        
        boolean[][] isValid = new boolean[c1.length+1][c2.length+1];
        
        isValid[0][0] = true;
        for (int i=1 ; i<=c1.length ; i++) isValid[i][0] = isValid[i-1][0] && c1[i-1] == c3[i-1];
        for (int i=1 ; i<=c2.length ; i++) isValid[0][i] = isValid[0][i-1] && c2[i-1] == c3[i-1];

        for (int i=1 ; i<=c1.length ; i++)
            for (int j=1 ; j<=c2.length ; j++)
                isValid[i][j] = (isValid[i - 1][j] && c1[i - 1] == c3[i + j - 1]) 
                		|| (isValid[i][j - 1] && c2[j - 1] == c3[i + j - 1]);
        
        return isValid[c1.length][c2.length];
    }
}