LeetCode —— Interleaving String

링크:http://leetcode.com/onlinejudge#question_97
원제:
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.
생각:
처음에 재 귀 를 사용 하면 생각 이 직관 적 이지 만 작은 데 이 터 는 시간 을 초과 할 수 있다.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.size() + s2.size() != s3.size())
            return false;
        return isInterleave(s1, 0, s2, 0, s3, 0);
    }
    
private:
    bool isInterleave(const string &s1, int i1,
        const string &s2, int i2, const string &s3, int i3) {
        
        if (i3 == s3.size())
            return true;
        
        if (i1 < s1.size() && s1[i1] == s3[i3]) {
            if (isInterleave(s1, i1+1, s2, i2, s3, i3+1))
                return true;
        }
        
        if (i2 < s2.size() && s2[i2] == s3[i3]) {
            if (isInterleave(s1, i1, s2, i2+1, s3, i3+1))
                return true;
        }
        
        return false;
    }
};

그래서 상 태 를 기록 하기 위해 서 배열 을 만 들 수 밖 에 없어 요.
S3. size = n 에 대해 서 는 x 길이 의 S1 과 y 길이 의 S2 가 교차 하여 구 성 될 수 있 는 지 여 기 는 x + y = n 입 니 다.
두 가지 방식 으로 만 도착 할 수 있 습 니 다.
1） array[x-1][y] --> array[x][y], if S1[x] == S3[n]
2)    array[x][y-1] --> array[x][y], if S2[y] == S3[n]

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (s1.size() + s2.size() != s3.size())
            return false;
        vector<vector<bool> > array;
        for (int i=0; i<=s1.size(); i++) {
            array.push_back(vector<bool>(s2.size()+1, false));
        }
        array[0][0] = true;
        for (int n=1; n<=s3.size(); n++) {
            for (int x=0, y=n; x<=n; x++, y--) {
                if (x>=0 && x<=s1.size() && y>=0 && y<=s2.size()) {
                    if ( (x-1 >= 0 && array[x-1][y] && s3[n-1]==s1[x-1]) ||
                         (y-1 >= 0 && array[x][y-1] && s3[n-1]==s2[y-1]) )
                        array[x][y] = true;
                    else
                        array[x][y] = false;
                }           
            }
        }
        return array[s1.size()][s2.size()];
    }
};

물론 공간 적 으로 최적화 할 수 있다.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function    
        if (s1.size() + s2.size() != s3.size())
            return false;
        
        if (s1.size() == 0 || s2.size() == 0) {
            if (s1 == s3 || s2 == s3)
                return true;
            return false;
        }
            
        vector<bool> vec(s2.size() + 1);
        vector<vector<bool> > state;
        state.push_back(vec);
        state.push_back(vec);
        
        int cur = 0;
        int pre = 1;
        state[cur][0] = true;
        for (int i=0; i<s2.size(); i++)
            if (s2[i] == s3[i])
                state[cur][i+1] = true;
            else
                break;
        
        for (int i=0; i<s1.size(); i++) {
            cur = (cur + 1) % 2;
            pre = (pre + 1) % 2;
            if (state[pre][0] && s1[i] == s3[i])
                state[cur][0] = true;
            else
                state[cur][0] = false;
            
            for (int j=0; j<s2.size(); j++) {
                if ((s1[i] == s3[i+j+1] && state[pre][j+1]) || (s2[j] == s3[i+j+1] && state[cur][j]))
                    state[cur][j+1] = true;
                else
                    state[cur][j+1] = false;
            }
        }
        
        return state[cur].back();
    }
};