[Leet code - 72] Edit Distance ❌

Edit Distance - LeetCode

문제

Input : 문자열 word1, word2

Output : word1을 word2로 변환하는 최소 연산 개수

 

※연산은 다음 세 가지 연산을 의미한다.

1. Insert / 2. Delete / 3. Replace( 특정 위치의 알파벳을 다른 알파벳으로 변경 )

 

 

시간 복잡도

※1초에 1억 번을 대략적인 기준으로 삼는다.

 

 

$1 \le n \le 500$

• $O(n^2) = 250'000$ ✅

 

해결 계획

문제 잘못 이해해서 뻘짓 한 문제로, Replace가 아닌 Swap으로 착각했지만, 깨달은 건 문제를 포기한 후 였다..

 

우선 언제 추가하고 언제 삭제하고 언제 변환해야 할지에 대해 고민하다가,

먼저 삽입 삭제로 알파벳 개수를 맞추고 swap을 진행하면 되지 않을까? 생각했지만

삽입 삭제를 함으로써 swap을 하지 않아도 되는 경우가 있지 않을까해서 다른 방법을 생각했다.

 

고민하다가 각 문자마다 세 가지 연산을 했을 때 나오는 단어들을 모두 저장? 하는 방식(DFS, BFS)이 아닐까 했지만,
정한 시간이 다 되어 포기했다.

 

 

되돌아보기

문제를 잘못 이해해지만 각 문자마다 세 가지 연산을 하는 모든 경우의 수를 고려해보는 계획은 정답과 비슷했다.

근데 이제 엄청난 경우의 수에 막혀 뇌도 막혀있었는데, 중복연산 이라는 키워드를 생각해 냈다면 ,
중복 연산을 줄이는 기법인 DP로 잘 전환하지 않았을까 싶다.

 

다음에는 이런 과정으로 좀 접근을 하면 좋을 듯 하다.

모든 경우의 수를 고려해야 한다.

⬇

경우의 수가 너무 많다.

⬇

중복 상태가 존재한다.

⬇

DP

 

 

핵심 아이디어

word1의 부분 문자열을 word2의 부분문자열로 만드는 횟수다.

dp[i][j] = word1의 i번째에서 word2의 j번째까지 만드는 최소 횟수

※dp[i - 1][dp[j - 1]까지는 같다고 가정하므로 word1의 i와 word2의 j만 비교한다.

 

초기 값

word1 : "AB" , word2 : "BCD"로 예시를 들어본다.

초기값으로 빈 문자열에서 BCD의 부분 문자열로 변환하는 횟수를 삽입한다.

빈 문자열이므로 변환하려는 문자열의 길이만큼의 삽입, 삭제가 곧 최소 횟수가 된다.

word1 \ word2	" "	B	C	D
" "	0	1	2	3
A	1
B	2

 

테이블 채우기

 

구현 코드

추후 재 풀이 후 작성 예정