LeetCode-0712

79 · 最长公共子串（中等）

public class Solution {
   
    public int longestCommonSubstring(String a, String b) {
        
        int n = a.length();
        int m = b.length();

        int dp[][] = new int[n+1][m+1];
        int max = 0;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(a.charAt(i-1)==b.charAt(j-1))dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] = 0;
                if(dp[i][j]>max)max = dp[i][j];
            }
        }

        return max;
    }
}

583. 两个字符串的删除操作(中等)

思路：最长公共子序列

class Solution {
    public int minDistance(String word1, String word2) {
        
        int n = word1.length();
        int m = word2.length();

        int dp[][] = new int[n+1][m+1];

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;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 n+m-2*dp[n][m];
    }
}

72. 编辑距离(困难)

class Solution {
    public int minDistance(String word1, String word2) {

        int n = word1.length();
        int m = word2.length();

        int dp[][] = new int[n+1][m+1];

        for(int i=1;i<=n;i++)dp[i][0] = i;
        for(int j=1;j<=m;j++)dp[0][j] = j;

        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(word1.charAt(i-1)==word2.charAt(j-1))dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
            }
        }
        return dp[n][m];
    }
}

647. 回文子串（中等）

class Solution {
    public int countSubstrings(String s) {

        int n = s.length();
        int cnt = n;

        boolean dp[][] = new boolean[n][n];

        for(int i=0;i<n;i++)dp[i][i] = true;

        for(int l=2;l<=n;l++){
            for(int i=0;i<n;i++){
                int j = i+l-1;
                if(j>=n)break;
                if(s.charAt(j)==s.charAt(i)){
                    if(l==2)dp[i][j] = true;
                    else dp[i][j] = dp[i+1][j-1];
                }
                if(dp[i][j])cnt++;
            }
        } 
        return cnt;
    }
}

516. 最长回文子序列(中等)

class Solution {
    public int longestPalindromeSubseq(String s) {
        
        int n = s.length();
        int dp[][] = new int[n+1][n+1];
        for(int i=0;i<=n;i++)dp[i][i] = 1;

        for(int l=2;l<=n;l++){
            for(int i=1;i<=n;i++){
                int j = i+l-1;
                if(j>n)break;
                if(s.charAt(j-1)==s.charAt(i-1)){
                    if(l==2)dp[i][j] = 2;
                    else dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i][j-1],dp[i+1][j]);
                }
            }
        } 
        return dp[1][n];
    }
}