동적 계획(문자열 편집) - 두 문자열의 문자를 동일하게 삭제

두 문자열의 문자를 동일하게 삭제
583. Delete Operation for Two Strings (Medium)

Input: "sea", "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

제목 설명:
  에는 두 문자열이 있는데 두 문자열의 자모를 삭제하여 두 문자열이 같게 합니다. 몇 개의 자모를 삭제하시겠습니까?
사고 분석:
이 문제를 두 문자열의 가장 긴 공통 서열 문제로 바꿀 수 있습니다.
코드:

class Solution {
    public int minDistance(String word1,String word2){
    int m=word1.length();
    int n=word2.length();
    int [][]dp=new int [m+1][n+1]; //dp[i][j],  word1  i    word2  j           
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(word1.charAt(i-1)==word2.charAt(j-1)){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    return m+n-2*dp[m][n];
}
}

전재 대상:https://www.cnblogs.com/yjxyy/p/11121631.html