1. 서로 다른 부분 수열의 개수 구하기

두 개의 문자열 text와 pattern이 주어졌을 때, text의 부분 수열 중 pattern과 일치하는 경우의 수를 계산하는 문제입니다. 부분 수열이란 원본 문자열에서 문자의 상대적 순서를 유지한 채 일부 문자를 제거하여 만들 수 있는 새로운 문자열을 의미합니다. 결과값은 32비트 부호 있는 정수 범위를 보장합니다.

class Solution {
public:
    int numDistinct(string text, string pattern) {
        int m = text.length();
        int n = pattern.length();
        vector<vector<uint64_t>> matchCount(m + 1, vector<uint64_t>(n + 1, 0));
        
        for (int i = 0; i <= m; ++i) {
            matchCount[i][0] = 1;
        }
        
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text[i - 1] == pattern[j - 1]) {
                    matchCount[i][j] = matchCount[i - 1][j - 1] + matchCount[i - 1][j];
                } else {
                    matchCount[i][j] = matchCount[i - 1][j];
                }
            }
        }
        return matchCount[m][n];
    }
};

2. 두 문자열을 동일하게 만들기 위한 최소 삭제 연산

두 문자열 strA와 strB가 주어졌을 때, 두 문자열을 동일하게 만들기 위해 필요한 최소 삭제 횟수를 구하는 문제입니다. 한 번의 연산으로 두 문자열 중 하나에서 임의의 문자 하나를 삭제할 수 있습니다.

예시:

• 입력: "sea", "eat"
• 출력: 2
• 설명: "sea"에서 's'를 삭제하여 "ea"로 만들고, "eat"에서 't'를 삭제하여 "ea"로 만듭니다.

class Solution {
public:
    int minDistance(string strA, string strB) {
        int lenA = strA.size();
        int lenB = strB.size();
        vector<vector<int>> deleteOps(lenA + 1, vector<int>(lenB + 1, 0));
        
        for (int i = 0; i <= lenA; ++i) deleteOps[i][0] = i;
        for (int j = 0; j <= lenB; ++j) deleteOps[0][j] = j;
        
        for (int i = 1; i <= lenA; ++i) {
            for (int j = 1; j <= lenB; ++j) {
                if (strA[i - 1] == strB[j - 1]) {
                    deleteOps[i][j] = deleteOps[i - 1][j - 1];
                } else {
                    deleteOps[i][j] = 1 + min(deleteOps[i - 1][j], deleteOps[i][j - 1]);
                }
            }
        }
        return deleteOps[lenA][lenB];
    }
};

3. 최소 편집 거리 계산

두 문자열 source와 target이 주어졌을 때, source를 target으로 변환하는 데 필요한 최소 연산 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음 세 가지입니다.

• 문자 삽입
• 문자 삭제
• 문자 교체

예시 1:

• 입력: source = "horse", target = "ros"
• 출력: 3
• 설명: horse -> rorse ('h'를 'r'로 교체) -> rose ('r' 삭제) -> ros ('e' 삭제)

예시 2:

• 입력: source = "intention", target = "execution"
• 출력: 5
• 설명: intention -> inention ('t' 삭제) -> enention ('i'를 'e'로 교체) -> exention ('n'을 'x'로 교체) -> exection ('n'을 'c'로 교체) -> execution ('u' 삽입)

제약 조건:

• 문자열의 길이는 0 이상 500 이하입니다.
• 모든 문자는 소문자 영어 알파벳으로 구성됩니다.

class Solution {
public:
    int minDistance(string source, string target) {
        int srcLen = source.length();
        int tgtLen = target.length();
        
        vector<vector<int>> editCost(srcLen + 1, vector<int>(tgtLen + 1, 0));
        
        for (int i = 0; i <= srcLen; ++i) editCost[i][0] = i;
        for (int j = 0; j <= tgtLen; ++j) editCost[0][j] = j;
        
        for (int i = 1; i <= srcLen; ++i) {
            for (int j = 1; j <= tgtLen; ++j) {
                if (source[i - 1] == target[j - 1]) {
                    editCost[i][j] = editCost[i - 1][j - 1];
                } else {
                    int replaceOp = editCost[i - 1][j - 1];
                    int deleteOp = editCost[i - 1][j];
                    int insertOp = editCost[i][j - 1];
                    editCost[i][j] = 1 + min({replaceOp, deleteOp, insertOp});
                }
            }
        }
        return editCost[srcLen][tgtLen];
    }
};