[leetcode]Interleaving String解題レポート

タイトルリンク:https://leetcode.com/problems/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.
構想:2 Dダイナミックプランニングの問題、dp[i][j]はs 1[0,i-1]サブストリングとs 2[0,j-1]サブストリングがs 3[0,i+j-1]サブストリングと一致するかどうかを表す
2つの状況に分けて議論します.
1.s 3[i+j-1]=s 1[i-1]の場合、dp[i][j]=dp[i-1][j]、すなわち、s 3[i+j-1]とs 1[i-1]が等しい場合、dp[i][j]の状態は、等位を除いたサブ状態dp[i-1][j]によって決まる
2.s 3[i+j-1]=s 2[j-1]の場合、dp[i][j]=dp[i][j-1]、すなわち、s 3[i+j-1]がs 2[j-1]と等しい場合、dp[i][j]の状態は、等位を除いたサブ状態dp[i][j-1]によって決まる
この2つの状態は1つが真であればdp[i][j]が真である.
初期条件:
dp[i][0] = dp[i-1][0] && (s1[i-1] == s3[i-1])
dp[0][j] = dp[0][j-1] && (s2[j-1] == s3[j-1])
別の列が空の状態では、この列とs 3は各ビットが等しくなければ変換できないので、前の列が等しくなければ次のビットは等しくないと理解できる.
具体的なコードは以下の通りです.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if(s3.size() != (s1.size() + s2.size()))
            return false;
            
        bool dp[s1.size()+1][s2.size()+1];
        dp[0][0] = 1;
        for(int i = 0; i < s1.size(); i++)
            dp[i+1][0] = (s1[i] == s3[i] && dp[i][0]);

        for(int i = 0; i < s2.size(); i++)
            dp[0][i+1] = (s2[i] == s3[i]&& dp[0][i] );
            
        for(int i =1; i<= s1.size(); i++)
        {
            for(int j =1; j <= s2.size(); j++)
            {
                bool ans1 =false, ans2 = false;
                if(s3[i+j -1] == s1[i-1])
                    ans1 = dp[i-1][j];
                if(s3[i+j-1] == s2[j-1])
                    ans2 = dp[i][j-1];
                
                dp[i][j] = ans1 || ans2;
            } 
        }  

        return dp[s1.size()][s2.size()];
    }
};