97. Interleaving String - Medium

前往題目

思路

這題畫二維陣列會清楚許多

1. 檢查s1和s2的長度加起來是否和s3一樣長，因為s1和s2是組成s3的所有部分
2. dp二維陣列，一維與二維，指的是s1和s2的指針，true代表當前取的s1和s2可以成功組成s3的一部分，false則不行
3. dp的確定條件是dp[s1的長度][s2的長度]為true，因為那個位置代表s1和s2都看過一遍，可以成功組成s3
4. 從後往前疊代，由dp的確定條件慢慢往上推論

關鍵就是一個字母一個字母來看，而不用分辨是s1的片段還是是s2的

Code

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        // s3 should be made of s1 and s2
        if (s1.length() + s2.length() != s3.length()) return false;

        // Extra column and row for algo.
        boolean[][] dp = new boolean[s1.length() + 1][s2.length() + 1];

        // The end will be always be true if both pointer can reach
        dp[s1.length()][s2.length()] = true;
        
        // bottom-up
        for (int i = s1.length(); i >= 0; --i) {
            for (int j = s2.length(); j >= 0; --j) {
                // 確保i和j在s1,s2範圍內
                // dp[i+1][j]代表當前我們已經用過了，要用下一個，如果是true那當前變為true才有意義，代表目前都是valid的
                if (i < s1.length() &&
                        s1.charAt(i) == s3.charAt(i + j) &&
                        dp[i + 1][j]) {
                    dp[i][j] = true;
                }
                if (j < s2.length() &&
                        s2.charAt(j) == s3.charAt(i + j) &&
                        dp[i][j + 1]) {
                    dp[i][j] = true;
                }
            }
        }

        return dp[0][0];
    }
}