Thursday, June 12, 2014

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.

[Thoughts]:
String,还是match string类的,首先应该想到的就是DP吧。
match[i][j] = true, if s1(0, i-1)  和 s2(0, j-1) 成功match s3(0, i+j-1).
match长度设为s1和s2的长度加一,便于实现和计算。
match[i][0] = true, if s1(0, i-1) == s3(0, i-1)

public class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        if(s1.length()==0 && s2.length()==0 && s3.length()==0)
            return true;// 这个if对应match【0】【0】情况,可以省去。
        if(s1.length()==0 || s2.length()==0)
            return s1.length()==0 ? s2.equals(s3) : s1.equals(s3);
        if(s1.length()+s2.length()!=s3.length())
            return false;
        
        boolean[][] match = new boolean[s1.length()+1][s2.length()+1];
        match[0][0] = true;
        
        for(int i=1; i<=s1.length(); i++)// 初始化只用s1情况
            match[i][0] = s1.charAt(i-1)==s3.charAt(i-1) ? match[i-1][0] : false;

        for(int j=1; j<=s2.length(); j++)// 初始化只用s2情况
            match[0][j] = s2.charAt(j-1)==s3.charAt(j-1) ? match[0][j-1] : false;
            
        for(int i=1; i<=s1.length(); i++){
            for(int j=1; j<=s2.length(); j++){
                match[i][j] = (s3.charAt(i+j-1)==s1.charAt(i-1) && match[i-1][j]) || (s3.charAt(i+j-1)==s2.charAt(j-1) && match[i][j-1]);
            }
        }
        
        return match[s1.length()][s2.length()];
        
    }
}

No comments:

Post a Comment