Interleaving String@LeetCode

LeetCode

Word count: 567 / Reading time: 3 min

 2015/04/17   Share

Interleaving String

动态规划题。用一个二维（也可以简化成一维的）boolean数组match[i][j]来表示str3.substring(0, i + j)能不能由str1.substring(0, i)和str2.substring(0, j)组成，递推公式：

1	match[i][j] = (match[i - 1][j] && str1.charAt(i - 1) == str3.charAt(i + j)) \|\| (match[i][j - 1] && str2.charAt(j - 1) == str3.charAt(i + j))

需要注意的是，这里的match中，第一行代表了用str1去组成str3的情况，而第一列代表了用str2去组成str3的情况，这是为了方便循环中的递推计算，所以要注意match中的索引和str1以及str2中的索引并不是直接对应的。

最后，怎么把这个二维的DP优化成一维的呢，其实只要记住一个简单的道理：在递推公式中，dp[i][j]的计算不依赖dp[i - 1][j - 1]，那么这个二维DP就可以优化成一维的。因为在计算dp[i][j]时，dp[i - 1][j]和dp[i][j - 1]本来就是已知的。那么如果计算需要依赖dp[i - 1][j - 1]，还能优化吗？形式上可以，那就是在循环内用两个数组，前一个数组记录dp中上一行的结果，后一个数组用来计算当前行的，但其实这个方法并没有对内存进行太多优化，因为Java对于垃圾回收并不是发生在对象引用计数归0的那一刻，而是会选取一个时间进行统一回收，所以这种优化，该分配的内容一样还是分配出去了，并且本身一维数组的直观程度不如二维来得好，所以这种优化并不提倡。

实现代码：

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

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/04/17/interleaving-string-at-leetcode/

发表日期: April 17th 2015, 10:18:00 am

Next Post

Recover Binary Search Tree@LeetCode
Previous Post

Scramble String@LeetCode

CATALOG

1. Interleaving String

