10-10: 두 문자열 사이의 거리

두 문자열 사이의 거리

 

문제

---

두 문자열 A, B 가 주어질 때, 두 문자열 사이의 거리를 구하려 한다. 여기서 거리는 다음과 같이 정의된다. 문자열 A가 주어질 때, 여기서 하나의 연산은 하나의 알파벳을 삽입 또는 삭제하는 것을 의미한다. 문자열 A와 B 사이의 거리란, A에서 시작하여 B를 만들기 위한 최소 연산의 횟수로 정의된다. 예를 들어, 문자열 A가 “abcabcd”이고, 문자열 B가 “abccabc” 라면, 문자열 A와 B 사이의 거리는 2가 된다. 왜냐하면 문자열 A의 세 번째에 ‘c’를 삽입하고, 가장 마지막에 있는 ‘d’를 삭제하면 문자열 B를 얻기 때문이다. 두 문자열이 주어질 때, 두 문자열 사이의 거리를 출력하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄과 두 번째 줄에 문자열이 주어지며, 이 문자열의 길이는 200을 넘지 않는다.  

출력

---

두 문자열 사이의 거리를 출력한다.

 

예제 입력

abcabcd
abccabc

예제 출력

2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class dp_string_distance {

    /**
     * 두 문자열 사이의 거리
     * 문제:
     * 두 문자열 A, B 가 주어질 때, 두 문자열 사이의 거리를 구하려 한다. 여기서 거리는 다음과 같이 정의된다.
     * 문자열 A가 주어질 때, 여기서 하나의 연산은 하나의 알파벳을 삽입 또는 삭제하는 것을 의미한다. 문자열 A와 B 사이의 거리란, A에서 시작하여 B를 만들기 위한 최소 연산의 횟수로 정의된다. 예를 들어, 문자열 A가 “abcabcd”이고, 문자열 B가 “abccabc” 라면, 문자열 A와 B 사이의 거리는 2가 된다.
     * 왜냐하면 문자열 A의 세 번째에 ‘c’를 삽입하고, 가장 마지막에 있는 ‘d’를 삭제하면 문자열 B를 얻기 때문이다. 두 문자열이 주어질 때, 두 문자열 사이의 거리를 출력하는 프로그램을 작성하시오.
     *
     * 입력:
     *
     *
     * 출력:
     *
     *
     * 예제 입력:
     *
     *
     * 예제 출력:
     *
     *
     * @param args
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();

        int[][] dp = new int[s1.length()+1][ s2.length()+1];

        //Initial condition:
        for (int i=0; i<=s1.length(); i++){
            dp[i][0] = i;
        }

        for (int i=0; i<=s2.length(); i++){
            dp[0][i] = i;
        }

        for (int i=1; i<=s1.length(); i++){
            for (int j=1; j<=s2.length(); j++){
                if (s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1];
                } else{
                    int insertDistance = dp[i][j-1] + 1;
                    int deleteDistance = dp[i-1][j] +1;
                    dp[i][j] = Math.min(insertDistance, deleteDistance);
                }
            }
        }

        System.out.println(dp[s1.length()][s2.length()]);



    }
}