하위 시퀀스sub sequence 질문, 예: 가장 긴 공통 하위 시퀀스, [LeetCode] Distinct Subsequences(하위 시퀀스 개수 구함)

인용문

하위 서열과 하위 문자열이나 연속 서브집합의 다른 점은 하위 서열이 원래 서열의 연속 값이 필요하지 않다는 것이다.
하위 서열의 제목에 대해 대부분은DP의 사상을 필요로 하기 때문에 상태 이동이 관건이다.
여기에 두 개의 흔히 볼 수 있는 서열 문제와 그 해법을 발췌하였다.
 

예제 1, 가장 긴 공통 서열

우리는 가장 긴 공공 서브열의 구법을 알고 있다. 먼저 복습해 보자. 그의 구법도 DP 사상을 사용한다. 문자열 s1과 문자열 s2에 대해 m[i][j]로 s1에서 s1[i]로 끝나는 서브열과 s2에서 s2[j]로 끝나는 서브열의 가장 긴 공공 서브열의 길이는 공공 서브열의 연속이어야 하기 때문에 상태 이동 방정식: m[i, j]=(s1[i]=s2[j]? m[i-1, j-1]+1:0).m[i, j]의 계산은 m[i-1, j-1]만 사용하고 그 전의 계산은 필요 없기 때문에 우리는 2차원 그룹으로 전체 m[s1.length()][s2.length()]를 저장할 필요가 없다. m[i-1, j-1]만 저장하고 계속 업데이트하면 된다.
코드:

char *LCString(const char* s1, const char* s2){
    if(NULL == s1 || NULL == s2)
        return NULL;
    int size1 = 0, size2 = 0;
    const char* head1 = s1; const char* head2 = s2;
    while(*(head1++) != '\0') size1++;
    while(*(head2++) != '\0') size2++;
    printf("%d, %d
", size1, size2);
    
    int maxlen = 0, maxend = 0, i = 0, j = 0, tmpPre = 0;
    int m2[size2];
    for(i = 0; i < size2; m2[i] = 0, ++i);
    for(i = 0; i < size1; ++i){
        for(j = 0; j < size2; ++j){
            int len = ((s1[i] == s2[j] ? 1 : 0) + (j > 0 ? tmpPre : 0));
            if(len > maxlen) { maxlen = len; maxend = i;}
            tmpPre = m2[j];
            m2[j] = len;
        }
    }
    
    if(maxlen > 0){//        
        char* lcs = new char[maxlen + 1];
        for(i = 0; i < maxlen; lcs[maxlen - i - 1] = s1[maxend - i], i++);
        lcs[maxlen] = '\0';
        return lcs;
    }
    return NULL;
}

 
 
그렇다면 가장 긴 공공 서열에 대해 어떻게 구합니까?
우선, m[][]로 길이를 저장하면 마지막에 최장자 서열을 제시하는 것은 좀 번거롭다. 왜냐하면 서열은 연속적이지 않기 때문이다.하지만 귀찮아도 괜찮아요.
이어서 m[i, j]가 s1[i]의 끝 문자열과 s2[j]의 끝 문자열의 가장 긴 공공 서열의 길이를 나타낸다고 가정한다. 
그러면:
만약에 s1[i]=s2[j], m[i, j]=m[i-1][j-1]+1;
만약 s1[i]!=s2[j],m[i,j] = Max(m[i-1][j], m[i][j-1]).
여기서 m[i, j]를 구할 때 m[i-1][j], m[i][j-1], m[i-1][j-1]을 모두 사용할 수 있기 때문에 우리는 좀 성실하게 2차원 그룹을 사용하자.

template <typename T> T* Lcseq(T* list1, int size1, T* list2, int size2){
    if(NULL == list1 || NULL == list2)
        return NULL;
    int** m = new int*[size1];
    int i = 0, j = 0;
    int max = 0, maxi = 0, maxj = 0;
    for(; i < size1; i++){
        m[i] = new int[size2];
        for(j = 0; j < size2; j++){
            if(i == 0 && j == 0) m[0][0] = (list1[0] == list2[0] ? 1 : 0);
            else if(i == 0) m[i][j] = (list1[i] == list2[j] ? 1 : m[i][j-1]);
            else if(j == 0) m[i][j] = (list1[i] == list2[j] ? 1 : m[i-1][j]);
            else m[i][j] = (list1[i] == list2[j] ? m[i-1][j-1] + 1 : (m[i][j-1] > m[i-1][j] ? m[i][j-1] : m[i-1][j]));
            if(m[i][j] > max){
                max = m[i][j];
                maxi = i;
                maxj = j;
            }
        }
    }
    //printf("%d, %d, %d
", max, maxi, maxj);
    
    //          
    int p1 = maxi, p2 = maxj, p = max;
    T* sub = new T[max];
    while(p1 >= 0 && p2 >= 0){
        
        if(list1[p1] == list2[p2]){
            sub[--p] = list1[p1];
            //printf("p: %d, p1: %d, p2: %d
", p, p1, p2);
            p1--;
            p2--;
        }    
        else{
            if(p1 == 0) p2--;
            else if(p2 == 0) p1--;
            else{
                if(m[p1-1][p2] < m[p1][p2-1]) p2--;
                else p1--;
            }
        }
        
    }
    return sub;    
}

 
 

예제 2, 서열의 개수를 구하고LeetCode

Distinct Subsequences
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,  "ACE"  is a subsequence of  "ABCDE"  while  "AEC"  is not).
Here is an example:S =  "rabbbit" , T =  "rabbit"
Return  3 .

class Solution {
public:
    int numDistinct(string S, string T) {
    }
};

 
 
DP를 사용하지 않으면 기억이 있는 귀환도 할 수 있다. 시간이 비교적 길고 귀환은 추가 창고 공간이 필요하다.

class Solution {
public:
    int numDistinct(string S, string T) {
        if(T.length() == 0) return 1;
        if(S.length() == 0) return 0;
        
        rec = new int*[S.length()];
        for(int i = 0;i < S.length(); ++i){
            rec[i] = new int[T.length()];
            for(int j = 0;j < T.length(); ++j)
                rec[i][j] = -1;
        }
        return numDistinctCore(S, T, 0 ,0);
    }
    
    int numDistinctCore(string S, string T, int p1, int p2) {
        if(p2 == T.length()) return 1;
        if((T.length()-p2) > (S.length()-p1)) return 0;
        if(rec[p1][p2] >= 0) return rec[p1][p2];
        int sum = 0;
        for(int i = p1;i < S.length(); ++i){
            if(S[i] == T[p2])
                sum += numDistinctCore(S, T, i+1, p2+1);
        }
        rec[p1][p2] = sum;
        return sum;
    }
private:
    int **rec;
};

AC 시간 388ms.
 
DP 사상을 도입하면 우리는 여전히rec[i][j]로'S[i] 엔딩 문자열'에'T[j] 엔딩 문자열'이 포함된 sequence 개수를 나타낸다.
S[i] 서브열은 S[i-1] 서브열을 포함하기 때문에rec[i][j]는 적어도rec[i-1][j]와 같다.또한 S[i]=T[j]가 있으면 S[i]와 T[j]를 일치시킬 수 있다. 이 경우 sequence 개수는rec[i-1][j-1]이다.
rec[i][j] = rec[i-1][j] + (S[i] == T[j] ? rec[i-1][j-1] : 0).
코드:

class Solution {
public:
    int numDistinct(string S, string T) {
        int slen = S.length(), tlen = T.length();
        if(slen < tlen) return 0;
        int **rec = new int*[slen+1];
        int i, j;
        for(i = 0; i <= slen; ++i){
            rec[i] = new int[tlen+1];
            for(j = 0; j <= tlen; ++j){
                rec[i][j] = 0;
            }
        }
        for(i = 0; i <= slen; rec[i++][0] = 1);
                
        for(i = 1; i <= slen; ++i){
            for(j = 1; j <= tlen; ++j){
                rec[i][j] = (rec[i-1][j] + (S[i-1] == T[j-1] ? rec[i-1][j-1] : 0));
            }
        }
        
        return rec[slen][tlen];
    }
};

AC 시간 52ms.대폭 인상하다.
 
위의 해법은 2차원수조를 사용했다.나중에 샤오레이고이 문제에 대한 해답를 찾아냈어요.j를 T의 끝에서 옮겨다니게 하면rec[i][j]는 여전히rec[i-1][j]와 같거나 변하지 않거나rec[i-1][j-1]을 붙여서 앞으로 옮겨다니기 때문에rec[i-1][j-1]은 덮어쓰지 않습니다.이렇게 하면 2차원 그룹을 생략하고 직접 1차원 그룹을 해결할 수 있다.T[j]의 끝에 있는 하위 문자열의 sequence 개수를 match[]로 표시합니다.
코드:

class Solution {
public:
    int numDistinct(string S, string T) {
        if(S.size() < T.size()) return 0;
        int match[T.size()+1];
        int i, j;
        for(match[0] = 1, i = 0; i < T.size(); match[++i] = 0);
        for(i = 1; i <= S.size(); ++i)
            for(j = T.size(); j >= 1; --j)
                if(S[i-1] == T[j-1])
                    match[j] += match[j-1];
        return match[T.size()];
    }
};

여기에도 이전 글에서 값이 덮어지지 않도록 뒤에서 앞으로 옮겨다니는 사상을 이용했다.
16ms AC, 토치카라고 할 수 밖에 없어요.