Leetcode의 두 문자열 일치

문자열의 일치 문제는 DP에 의존하여 풀어야 하는데 문제를 푸는 과정에서 귀속으로 완성할 수 있지만 대부분 TLE로 끝난다.나중에 분석해 보니 주로 매거하는 부분이 너무 많아서 매거 부담이 너무 크다.
제목 1: Interleaving String
Given s1, s2, s3, find whether s3 is formed by  the iterleaving of s1 and s2. 
사고방식1: 이 문제를 귀속적인 방법으로 해결하려면 아래 표로 각각 s1, s2, s3을 제어해야 한다. 마치 Merge와 같다.또 이것은 시비를 판단하는 문제이기 때문에 이 귀속은 값을 되돌려야 한다.

public class Solution {
    public boolean isInterleave(String s1, String s2, String s) {
        return isInterleave(s1, 0, s2, 0, s, 0);
    }


    public boolean isInterleave(String s1, int i1, String s2, int i2, String s, int i){
        if(i>=s.length()){
            if(i1>=s1.length() && i2>=s2.length()) return true;
            else    return false;
        }

        if(i1 < s1.length() && s1.charAt(i1)==s.charAt(i) && isInterleave(s1,i1+1,s2,i2,s,i+1))
            return true;

        if(i2 < s2.length() && s2.charAt(i2)==s.charAt(i) && isInterleave(s1,i1,s2,i2+1,s,i+1))
            return true;
        return false;
    }
}

사고방식2: 2차원수 그룹 DP[i][j]로 s1의 현재 길이가 i이고 s3의 현재 길이가 j이며 s2의 현재 길이가 j-i일 때 정확한지 여부를 나타낸다.(여기에서도 i, j로 각각 s1, s2의 현재 길이를 표시할 수 있습니다.)비망록을 확정했으니 추이 관계를 확정해야 한다.DP[i][j]의 하위 문제는 두 가지가 있습니다. DP[i][j-1]와 DP[i-1][j-1], DP[i][j-1]는 s2와 s3만 일치합니다. DP[i-1][j-1]는 s1과 s3이 일치했음을 나타냅니다.

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        const int n1=s1.length();
        const int n2=s2.length();
        const int n3=s3.length();
        if(n3!=n1+n2) return false;
        
        bool dp[n3+1][n2+1];
        for(int i=0; i<=n3; i++)
            for(int j=0; j<=n1; j++)
                dp[i][j]=false;
        dp[0][0]=true; 
        
        for(int i=0; i

class Solution {
public:
    bool isInterleave(string s1, string s2, string s3) {
        const int n1=s1.length();
        const int n2=s2.length();
        const int n3=s3.length();
        if(n3!=n1+n2) return false;

        bool dp[n1+1][n2+1];
        for(int i=0; i<=n1; i++)
            for(int j=0; j<=n2; j++)
                dp[i][j]=false;
        dp[0][0]=true; 
        
        for(int i=0; i<=n1; i++){
            for(int j=0;j<=n2; j++){  //s2 [0, n2] 
                if(dp[i][j]==false) continue;
                int k=i+j;
                if(s2[j]==s3[k]) 
                    dp[i][j+1]=true;
                if(s1[i]==s3[k]) 
                    dp[i+1][j]=true;
            }
        }
        return dp[n1][n2];
    }
};

여기에서 사용하는 후추의 형식을 주의해야 한다. 개인적으로 이곳의 후추가 전추보다 우세하다고 생각한다. 첫째, s1, s2, s3과 DP 간의 index는 별도의 교정이 필요하지 않다. 둘째, 후추는 서브 문제가true에서 점차적으로 해야 성립되기 때문이다. 그렇지 않으면 모두 헛소리이다. 그러나 이 안에 두 개의 서브 문제가 있고 후추는 한 번만 판독하면 된다.
제목 2: Edit Distance
Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. 3 operations are permitted: insert, delete, replace.
사고방식: 2차원 그룹 dp[i][j]로 길이가 i인 s1이 길이가 j인 s2로 전환할 때 필요한 최소 조작수를 나타낸다.dp[i][j]에는 세 가지 하위 문제가 있습니다. dp[i-1][j], dp[i][j-1]와 dp[i-1], dp[i-1][j]는 insert, dp[i][j-1]는 insert, dp[i-1][j]는 delete, dp[i-1][j-1]는 replace를 나타냅니다.

class Solution {
public:
    int minDistance(string word1, string word2) {
        const int m=word1.length();
        const int n=word2.length();
        
        int dp[m+1][n+1];
        for(int i=0; i<=m; i++) dp[i][0]=i;
        for(int i=0; i<=n; i++) dp[0][i]=i;
        
        for(int i=1; i<=m; i++){
            for(int j=1; j<=n; j++){
                int minDis=min(dp[i-1][j]+1, dp[i][j-1]+1);
                minDis=min(minDis, dp[i-1][j-1]+(word1[i-1]==word2[j-1]?0:1));
                dp[i][j]=minDis;
            }
        }
        return dp[m][n];
    }
};

제목 3: Distinct Subsequences
Given a string S and a strinig T, count the number of distinct subsequences of T in S. [subsequence is not substring!]
사고방식: 이 문제는 아마 DP로만 풀 수 있을 거예요. 귀속 따위로 손을 댈 수가 없어요.어려운 문제!dp[i][j]는 T(1.i)의 서로 다른 S(1.j) 서열을 나타냅니다.하위 문제는 두 가지 상황이 있는데 T[i]=S[j]일 때 S[j]를 계속 사용한다.ST[i]!=S[j], S[j]를 포기하고 S는 이전 순환을 계속합니다.

class Solution {
public:
    int numDistinct(string S, string T) {
        int n=S.length();
        int m=T.length();
        if(m>n) return 0;
        
        vector> num(n+1, vector(m+1, 0));
        for(int k=0; k<=n; k++) 
            num[k][0] = 1;    // initialization
        
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                num[i][j]=num[i-1][j]+(S[i-1]==T[j-1]?num[i-1][j-1]:0);
            }
        }
        return num[n][m];
    }
};

주의, n-1 단계만 갱신되기 때문에 2차원 수조를 바꾸면 1차원 수조로 퇴화할 수 있지만, 시간의 복잡도는 역시 O(mn)이다. 

class Solution {
public:
    int numDistinct(string S, string T) {
        int n=S.length();
        int m=T.length();
        if(m>n) return 0;
        vector num(m+1,0);
        num[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=m;j>0;j--){
                num[j]=num[j]+(S[i-1]==T[j-1]?num[j-1]:0);
            }
        }
        return num[m];
    }
};