[leetcode 문제풀이 노트] Edit Distance
5522 단어 LeetCode
You have the following 3 operations permitted on a word:
a) Insert a characterb) Delete a characterc) Replace a character
문제: 동적 기획 문제.
수조 dp[i][j]로word1[0,i]에서word2[0,j]로 바꾸는 데 필요한 최소 변환을 나타낸다.
그럼 dp[i][j]=word1(i)==word2(j)?dp[i-1][j-1]: min(dp[i-1,j], dp[i,j-1], dp[i-1,j-1])+1;
특히 주의해야 할 것은 첫 번째 줄과 첫 번째 열의 처리 문제다.한 가지 방법은 dp의 크기를 dp[word1.length+1][word2.length+1]로 설정한 다음에 dp[0][i]=dp[i][0]=i로 설정하여 빈 문자열에서 길이가 i인 문자열로 서로 변환하려면 적어도 i보가 필요하다는 것을 나타낸다.개인적으로 이것은 비교적 좋은 방법이라고 생각했지만 당시에는 생각하지 못했다.
내가 생각한 것은 또 다른 방법이었고, 게다가 이곳에서 오랫동안 구덩이에 빠졌다.행위 예: dp[0][i] = Math.max(dp[0][i-1] + (wordchars1[0]== wordchars2[i]?0:1),i);만약word1의 0자와word2의 i자와같다면 dp[0][i-1]보변환이 필요합니다.그러나 여기에는 문제가 하나 있다. 바로 word1="pneumu", word2="up"일 때, 이때 문자열'u'에서'pneum'으로 4단계가 필요하고, 계산에서'u'에서'pneumu'로 4단계가 필요하지만, 직접 dp[0][i-1]로 4단계가 필요하면 불가능하다. 두 문자열의 길이가 5단계, 적어도 5단계가 다르기 때문에 바깥의 max 함수 판단이 나온다.두 문자열이 서로 변환되는 최소 단계는 두 문자열의 길이보다 낮지 않습니다.
최종 코드는 다음과 같습니다.
1 public class Solution {
2 public int minDistance(String word1, String word2) {
3 int m = word1.length();
4 int n = word2.length();
5 if(m == 0)
6 return n;
7 if(n == 0)
8 return m;
9 int[][] dp = new int[m][n];
10
11 char[] wordchars1 = word1.toCharArray();
12 char[] wordchars2 = word2.toCharArray();
13
14 dp[0][0] = wordchars1[0] == wordchars2[0]?0:1;
15 for(int i = 1;i < n;i++)
16 dp[0][i] = Math.max(dp[0][i-1] + (wordchars1[0]== wordchars2[i]?0:1),i);
17 for(int i = 1;i < m;i++)
18 dp[i][0] = Math.max(dp[i-1][0] + (wordchars1[i]== wordchars2[0]?0:1),i);
19
20 for(int i = 1;i < m;i++){
21 for(int j = 1;j < n;j++){
22 if(wordchars1[i] == wordchars2[j] )
23 dp[i][j] = dp[i-1][j-1];
24 else{
25 dp[i][j] = 1 + Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
26 }
27 }
28 }
29
30 return dp[m-1][n-1];
31 }
32 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
