[Dynamic Programming][Medium] 72. Edit Distance

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

 

Q. 주어진 word1과 word2에 대해서 아래와 같이 수정을 할 수 있다고 하면, word1을 word2로 바꾸는데 필요한 최소한의 연산수를 구하라. 

 Insert 연산, Delete 연산, Replace 연산.

 

 

 

Solution. 

 우선 풀이 전에, 이 문제는 충분히 좋은 문제다. 

 실생활에 많이 적용될 여지가 있다. 

 

  문제에서 필요한 것은 연산을 가한 횟수다. 

  따라서 string의 실제 변환에는 관심이 없다. 

 

  또한 코드 로직은 사람처럼 직관적일 수 없으므로, 하나 하나 다 해 보면서 결과를 확인해 봐야 한다, 

  우선, 특정 위치에서 어떤 것들이 가능한지 생각해 보자. 

  일단 특정 위치의 두 문장의 캐릭터가 같다면 연산을 할 필요가 없다. 그냥 다음 위치로 둘다 이동하면 된다. 

  다르다면 위 세 연산을 모두 해 보면서 최소가 되는 연산을 반환하면 된다. 

  

  종료 조건이 조금 사고의 변환이 필요한데, 이 문제에서는 두 문장 중 하나의 문장에 대한 검사가 완료되면, 아직 완료되지 않은 쪽을 단순히 그만큼 위 세 연산을 통해 변경하면 되므로, 그 차이 만큼의 연산만 더 있으면 될 것이다. 

  

  vector를 통해 캐싱을 하고, 이를 코드로 작성해 본다. 

 

 

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

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

        if(word1[idx1] == word2[idx2])
            return vCache[idxCache] = minD_helper(word1, word2, vCache, idx1 + 1, idx2 + 1);

        int ins = 1 + minD_helper(word1, word2, vCache, idx1,     idx2 + 1);
        int del = 1 + minD_helper(word1, word2, vCache, idx1 + 1, idx2);
        int rep = 1 + minD_helper(word1, word2, vCache, idx1 + 1, idx2 + 1);

        del = min(ins, del);
        return vCache[idxCache] = min(rep, del);
    }

public:
    int minDistance(string word1, string word2) 
    {
        vector<int> vCache;
        vCache.resize(word1.size()*word2.size(), -1);
        return minD_helper(word1, word2, vCache, 0, 0);
    }

  

적절한 결과를 얻었다. 

 

Note) 초반 접근이 중요한 문제다. 

 string 변경과 전체 비교 등 string 변환으로 들어가면 복잡한 문제가 된다. 

 대신에, 문자를 같게 하기 위해 세 연산 중 연산이 1회 필요할 뿐임을 이해하고,

 연산에 따라 어떻게 index 위치를 증가시킬 것인지 등을 알아내면 수월하게 풀릴 것이다.