Delete Operation for Two Strings

두 문자열을 같게 만들려고 할 때, 한 단계에 하나의 문자열에서 한 문자를 지운다.

이 때 최소로 필요한 단계를 구하는 문제이다.

두 문자열에서 가장 긴 subsequnce를 구하고 두 문자와의 길이 차를 구하면 된다.

class Solution {
public:
    int minDistance(string word1, string word2) {
        
        int oneSize = word1.size();
        int twoSize = word2.size();
        
        int LCS[oneSize + 1][twoSize + 1];
        
        for (int i = 0; i < oneSize + 1; i++)
        {
            for (int j = 0; j < twoSize + 1; j++)
            {
                if (i == 0 || j == 0)
                {
                    LCS[i][j] = 0;
                }
                else if (word1[i - 1] == word2[j - 1])
                {
                    LCS[i][j] = LCS[i - 1][j - 1] + 1;
                }
                else
                {
                    LCS[i][j] = max(LCS[i - 1][j] , LCS[i][j - 1]);
                }
            }
        }
        
        int result = oneSize + twoSize - 2 * LCS[oneSize][twoSize];
        
        return result;    
    }
};