[LeetCode] 72. Edit Distance - 깊이우선탐색(DFS) JAVA

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

코드설명

깊이우선탐색(DFS) 를 활용합니다.

 

먼저, 함수를 정의합니다.

DFS(word1, word2, word1Idx, word2Idx) = word[0..word1Idx]와 word2[0..word2Idx] 가 서로 같을 떄 몇번의 연산과정을 통해 처리했는지를 반환한다.

 

추가적으로 2가지를 유의합니다.

1. 실제로 더하는 것이 아닌, 논리적으로 더하거나 삭제하거나 교체하거나 일치하거나를 체크합니다.

이를 위해서는 word1Idx와 word2Idx를 사용합니다.

( 이렇게 처리해야 하는 것 자체가 상상하는 것이 어려웠습니다. 일반적으로 직접 더해가면서 처리해가니깐요. )

word1Idx와 word2Idx를 통해서 [0..word1Idx] 에서 일치하는 단어를 확정해나가며, 진행합니다.

2. 최적 부분구조임을 알아야 합니다.

[0..word1Idx][0..word2Idx] 에서 여러가지 과정을 통해 [0.. wordIdx .. k][0.. word2Idx .. k]에 도달했을떄 이미 연산했다면, 바로 반환하여 처리합니다.

코드

정답코드1입니다.

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        int[][] cache = new int[word1.length() + 1][word2.length() + 1];
        for(int[] v : cache){
            Arrays.fill(v, -1);
        }
        return DFS(word1, word2, 0, 0, cache);
    }

    int DFS(String word1, String word2, int word1Idx, int word2Idx, int[][] cache){
        if(word1Idx == word1.length()) return word2.length() - word2Idx;
        if(word2Idx == word2.length()) return word1.length() - word1Idx;

        if(cache[word1Idx][word2Idx] != -1) return cache[word1Idx][word2Idx];

        if(word1.charAt(word1Idx) == word2.charAt(word2Idx)){
            return DFS(word1, word2, word1Idx + 1, word2Idx + 1, cache);
        } else {
            int insertOperation = DFS(word1, word2, word1Idx, word2Idx + 1, cache);
            int delOperation = DFS(word1, word2, word1Idx + 1, word2Idx, cache);
            int replaceOperation = DFS(word1, word2, word1Idx + 1, word2Idx + 1, cache);

            return cache[word1Idx][word2Idx] = 1 + Math.min(insertOperation, Math.min(delOperation, replaceOperation));
        }
    }


}