[DP-MultiDimensional][Medium] 72. Edit Distance

https://leetcode.com/problems/edit-distance/description

LeetCode - The World's Leading Online Programming Learning Platform

 

Question. 주개의 string word1과 word2가 주어질때, word1과 word2를 같게 만들기 위해 최소한의 필요한 연산 수를 구하라. 단, 아래와 같은 연산이 한번에 가능하다. 문자 당, 삭제, 추가, 교환 이 가능하다. 

 

 

 

Solution. 

 DP 중에서도 아주 흥미로운 축에 속하는 문제이다. 

 직관으로 풀기는 역시 쉽지 않은 문제이다. 

 

 우선 원하는 결과가 결과 문자가 아닌, 횟수라는 점에 주목한다. 즉, 어떻게 바꿔서 어떤 결과를 갖는지는 알필요 없다는 것이다. 

 우리는 해당 연산이 있을때 1번 operation을 했음을, 그리고 다음번에 어떤 것을 처리할지, 그것을 알아내는 것이 문제의 핵심이다 할 수 있겠다. 

 

 즉, 풀이 과정에서 문자가 다르면, 길이가 다른 쪽보다 크면 이런 연산은 사실상 의미 없다는 뜻이다. 

 

 우선,,, 역시 DP의 관점에서 한 지점에서 생각해 보자. 

 현재 두 문자가 같다면, 어떤 연산도 필요없다. operation 추가 없이, 두 string 다 다음 대상으로 넘어간다. 

 다르다면, 위 세 연산을 모두 시도 및 결과 비교를 할 필요가 있다. 연산은 첫번째(word1)을 기준으로 한다.

   교체 : word1의 대상을 word2의 대상(char)으로 교체하였다. 따라서 같다고 간주하고 둘다 다음 대상으로 이동.

   삽입 : word1에 word2의 대상과 같은 char를 넣었으므로, word1은 제자리, word2는 다음으로.

   삭제 : word1의 대상을 제거(무시)하였다. 따라서 word1은 다음으로, word2는 다시 연산을 위해 제자리.

  이 세 연산의 결과 중 최종 최소 값을 구한다. 

  (위 세 과정이 이해가 잘 안되면, 그림으로 그리면서 곱씹어 보자.)

 

 그렇다면 종료 조건은?

  word1의 현재가 word1의 모든 지점을 완료 했다면, 무엇을 반환할까? 

  당연하게도 word2가 남은 만큼, insert하는 것이 최소 이므로, 이 남은 만큼이 바로 잔여 연산 수가 된다. 

  word2에 대해서도 마찬가지 이다. 

 

 이를 그대로 로직으로 만들어 본다. 

 

int minDist_dp(int idx1, int idx2, string word1, string word2)
{
    if (idx1 >= word1.size())
        return word2.size() - idx2;
    if (idx2 >= word2.size())
        return word1.size() - idx1;

    if (word1[idx1] == word2[idx2])
        return minDist_dp(idx1 + 1, idx2 + 1, word1, word2);
    else
    {
        int insert_op = 1 + minDist_dp(idx1, idx2+1, word1, word2);
        int delete_op = 1 + minDist_dp(idx1+1, idx2, word1, word2);
        int replace_op = 1 + minDist_dp(idx1+1, idx2+1, word1, word2);

        return min(insert_op, min(delete_op, replace_op));
    }
}
int minDistance(string word1, string word2)
{
    if (word1.size() == 0)	return word2.size();
    if (word2.size() == 0)  return word1.size();

    return minDist_dp(0, 0, word1, word2);
}

 

묘하게도, Memory limit 오류가 발생. call stack이 너무 많이 쌓여 그런게 아닌가 생각된다.

캐싱 최적화를 해 본다. 

 

 

int minDist_dp(vector<int>& vCache, int idx1, int idx2, string word1, string word2)
{
    if (idx1 >= word1.size())
        return word2.size() - idx2;
    if (idx2 >= word2.size())
        return word1.size() - idx1;

    int idxCache = idx2 * word1.size() + idx1;
    if (vCache[idxCache] >= 0)
        return vCache[idxCache];

    if (word1[idx1] == word2[idx2])
        vCache[idxCache] = minDist_dp(vCache, idx1 + 1, idx2 + 1, word1, word2);
    else
    {
        int insert_op = 1 + minDist_dp(vCache, idx1, idx2+1, word1, word2);
        int delete_op = 1 + minDist_dp(vCache, idx1+1, idx2, word1, word2);
        int replace_op = 1 + minDist_dp(vCache, idx1+1, idx2+1, word1, word2);

        vCache[idxCache] = min(insert_op, min(delete_op, replace_op));
    }
    return vCache[idxCache];
}
int minDistance(string word1, string word2)
{
    if (word1.size() == 0)	return word2.size();
    if (word2.size() == 0)  return word1.size();

    // 2 factor모두에 대한 table 필요.
    vector<int> vCache;
    vCache.resize(word1.size() * word2.size(), -1);
    return minDist_dp(vCache, 0, 0, word1, word2);
}

 

결과. 

 

 

note : for loop을 사용한 bottom-up type도 시도 해 볼 것.