algorithm
거리 동적 알고리즘 편집

문자열 1을 문자열 2로 변환하는 데 필요한 최소 편집 수

문제 문장은 str1과 str2의 두 문자열을주고 str1에 대해 수행 할 수있는 연산의 최소 개수를 str2로 변환 한 것과 같습니다. 연산은 다음과 같습니다.

1. 끼워 넣다
2. 풀다
3. 바꾸다

예를 들어

Input: str1 = "geek", str2 = "gesek"
Output: 1
We only need to insert s in first string

Input: str1 = "march", str2 = "cart"
Output: 3
We need to replace m with c and remove character c and then replace h with t

이 문제를 해결하기 위해 우리는 2 차원 배열 dp [n + 1] [m + 1]을 사용합니다. 여기서 n은 첫 번째 문자열의 길이이고 m은 두 번째 문자열의 길이입니다. 예를 들어, str1이 azcef 이고 str2가 abcdef 이면 배열이 dp [6] [7]이고 최종 답은 dp [5] [6]에 저장됩니다.

          (a) (b) (c) (d) (e) (f)
     +---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
     +---+---+---+---+---+---+---+
  (a)| 1 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (z)| 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (c)| 3 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (e)| 4 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (f)| 5 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

DP의 경우 [1] [1] 우리는 우리가 0 .FOR DP있을 것입니다 .IT로 변환 위해 무엇을 할 수 있는지 확인해야 [1] [2] 우리는 우리가 AB .IT로 변환하기 위해 무엇을 할 수 있는지 확인해야 우리는 우리의 배열 모양을 1 회 반복 후, 낭포 b를 삽입하기 때문에 일을 할 것이다

          (a) (b) (c) (d) (e) (f)
     +---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
     +---+---+---+---+---+---+---+
  (a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (z)| 2 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (c)| 3 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (e)| 4 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (f)| 5 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+ 

반복 2

DP를 들어 [2] [1] 우리는 DP에 대한 .Similary을 (Z)을 제거하기 때문에, DP [2] [1]이 될 것이다 필요로 AZ 변환하는 것을 확인할 수있다 [2] [2] 우리는 Z 바꿔야 B를 따라서 DP [2] [2] 우리 DP [] 배열이 모양을 2 회 반복 한 후, 낭포 것이다.

         (a) (b) (c) (d) (e) (f)
     +---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
     +---+---+---+---+---+---+---+
  (a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (z)| 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (c)| 3 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (e)| 4 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+
  (f)| 5 |   |   |   |   |   |   |
     +---+---+---+---+---+---+---+

따라서 우리의 공식 은 다음과 같이 보일 것입니다.

if characters are same
    dp[i][j] = dp[i-1][j-1];
else
    dp[i][j] = 1 + Min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

마지막 반복 후 우리의 dp [] 배열은 다음과 같이 보입니다.

          (a) (b) (c) (d) (e) (f)
     +---+---+---+---+---+---+---+
     | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
     +---+---+---+---+---+---+---+
  (a)| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (z)| 2 | 1 | 1 | 2 | 3 | 4 | 5 |
     +---+---+---+---+---+---+---+
  (c)| 3 | 2 | 2 | 1 | 2 | 3 | 4 |
     +---+---+---+---+---+---+---+
  (e)| 4 | 3 | 3 | 2 | 2 | 2 | 3 |
     +---+---+---+---+---+---+---+
  (f)| 5 | 4 | 4 | 2 | 3 | 3 | 3 |
     +---+---+---+---+---+---+---+

Java로 구현

public int getMinConversions(String str1, String str2){
    int dp[][] = new int[str1.length()+1][str2.length()+1];
    for(int i=0;i<=str1.length();i++){
        for(int j=0;j<=str2.length();j++){
            if(i==0)
                dp[i][j] = j;
            else if(j==0)
                dp[i][j] = i;
            else if(str1.charAt(i-1) == str2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else{
                dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
            }
        }
    }
    return dp[str1.length()][str2.length()];
}

시간 복잡성

O(n^2)