Участник:Rublev.mv/minimum-ascii-delete-sum-for-two-strings

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution {
    public int minimumDeleteSum(String s1, String s2) {
        int n=s1.length();
        int m=s2.length();
        int len1 = 0;
        int len2 = 0;
 
        int[][] arr = new int[n+1][m+1];
        for(int i=1; i<=n; i++){
            arr[i][0] = arr[i-1][0] + (int)s1.charAt(i-1);
        }
        for(int j=1; j<=m; j++){
            arr[0][j] =arr[0][j-1] + (int)s2.charAt(j-1);
        }
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    arr[i][j] = arr[i-1][j-1];
                } else {
                    len1 = (int)s1.charAt(i-1);
                    len2 = (int)s2.charAt(j-1);
                    arr[i][j] = Math.min(arr[i-1][j]+len1, arr[i][j-1]+len2);
                    arr[i][j] = Math.min(arr[i][j], arr[i-1][j-1]+len1+len2);
                }
            }
        }
        return arr[n][m];
    } 
 
}