leetcode-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.
이 문제는 두 문자열이 합병되어 다른 새로운 문자열을 구성할 수 있는지 판단해야 한다. 이 합병은 질서정연한 합병이다. 바로 새로운 문자열에서 원래의 두 문자열과 각각 찾을 수 있고 자모의 순서는 원래의 두 문자열과 자모의 순서가 일치한다.
가령 s1의 길이가 n1이고 s2의 길이가 n2이라고 가정하면 s3의 모든 자모는 2가지 선택이 있다. 즉, s3의 첫 번째 자모는 s1에서 시작할 수도 있고 s2에서 시작할 수도 있다. 이렇게 하면 모두 s1과 s2에서 (n1+n2) 개의 수를 뽑아야 한다. 총 s3의 가능한 수는 n1+n2에서 n1개를 뽑아야 한다.
이것은 s3이 s1과 s2가 질서정연하게 합병될 수 있는지 판단하는 것이다.귀속으로 해답을 구하고 s3의 첫 번째 알파벳과 s1과 s2의 첫 번째 알파벳을 비교하기 쉽다. 만약에 s3[0]=s1[0]이 s3의 첫 번째 수를 s1에서 찾을 수 있다는 것을 설명한다면 s3 뒤의 문자열이 s1의 첫 번째 알파벳 뒤의 문자열과 s2로 합성될 수 있는지 계속 검색해야 한다.만약에 s3[0]=s2[0]라면 s3의 첫 번째 수도 s2에서 찾을 수 있음을 설명하고 s3 뒤에 있는 문자열을 s1과 s2의 첫 번째 자모로 묶을 수 있는지 계속 검색합니다.이렇게 차례로 돌아가면 답안을 산출할 수 있다.
그래서 간단한 귀속을 작성하면 다음과 같다.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.size() != s1.size()+s2.size())
            return false;
        return isInterleave(s1, 0, s2, 0, s3, 0);
    }
private:
    bool isInterleave(const string &s1, int b1, const string &s2, int b2, 
         const string& s3, int b3) {
        if (b1 == s1.size())   // s1 reaches end
            return s3.substr(b3) == s2.substr(b2);
        
        if (b2 == s2.size())   // s2 reaches end
            return s3.substr(b3) == s1.substr(b1);
        
         if (s3[b3] == s1[b1]) { //match s1
             if (isInterleave(s1, b1+1, s2, b2, s3, b3+1))
                 return true;
         }
         
         if (s3[b3] == s2[b2]) { //match s2
            if (isInterleave(s1, b1, s2, b2+1, s3, b3+1))
                return true;
         }
        
        return false;  // no match
    }
};

최종 결과는 TLE.위의 귀속 계산은 중복된 하위 작업을 많이 계산했기 때문에 기억화 검색으로 바꾸면 다음과 같다.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.size() != s1.size()+s2.size())
            return false;
        memset(hasSearched, false, sizeof(hasSearched));
        return isInterleave(s1, 0, s2, 0, s3, 0);
    }
private:
    bool isInterleave(const string &s1, int b1, const string &s2, int b2, 
         const string& s3, int b3) {
        if (b1 == s1.size())   // s1 reaches end
            return s3.substr(b3) == s2.substr(b2);
        
        if (b2 == s2.size())   // s2 reaches end
            return s3.substr(b3) == s1.substr(b1);
        
         if (s3[b3] == s1[b1]) { //match s1
             if (!hasSearched[b1+1][b2] && isInterleave(s1, b1+1, s2, b2, s3, b3+1))
                 return true;
         }
         
         if (!hasSearched[b1][b2+1] && s3[b3] == s2[b2]) { //match s2
            if (isInterleave(s1, b1, s2, b2+1, s3, b3+1))
                return true;
         }
        
        hasSearched[b1][b2] = true;
        return false;  // no match
    }
    
    bool hasSearched[100][100];
};

또한 계속 최적화할 수 있다. 예를 들어 s3 문자가 s1 문자와 같다는 것을 검출했을 때 s3 뒤의 한 문자가 s1, s2의 앞 문자와 같는지 먼저 판단할 수 있다. 만약 같지 않으면 이 경로는 걸어갈 필요가 없다.
사실 동적 기획으로 해답을 구할 수도 있다.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        if (s3.size() != s1.size()+s2.size())
            return false;
            
        bool d[200][200] = {false};    // d[i][j] s1 i s2 j s3 i+j 
        d[0][0] = true;   
            
        int len1=s1.size(), len2=s2.size();
        
        for (int i=0; i<=len1; ++i) {
            for (int j=0; j<=len2; j++) {
                
                if (s1[i]==s3[i+j] && d[i][j]==true) 
                    d[i+1][j] = true;
                
                if (s2[j]==s3[i+j] && d[i][j]==true)
                    d[i][j+1] = true;
            }
        }
        
        return d[len1][len2];
    }
    
};