动态规划题：最长回文子串、接雨水、正则匹配

一、最长回文子串

输入：ababc
输出：aba或者bab

输入：abcddcb
输出：bcddcb

判断一个回文子串的方法

如果一个字符串：abcba

判断其是否为回文子串的方法：

1. 开头和结尾不相同 -> 不是回文子串
2. 开头和结尾相同 -> 去掉开头和结尾是否是回文子串

代码：

public static boolean[][] longestProcess(String s){
    /*
         * 1. start and end
         * 2. length
         * 3. dp[i][j] = dp[i+1][j-1] (i+1 <= j-1)
         */

    boolean[][] dp = new boolean[s.length()][s.length()];
    // 1. "a"
    for (int i = 0; i < s.length(); i++) {
        dp[i][i] = false;
    }
    // length is value
    int maxLen = 1;
    int start = 0;
    char[] chars = s.toCharArray();
    for (int L = 2; L <= s.length(); L++){
        for (int i = 0; i < s.length(); i++) {
            int end = L + i - 1;
            if (end >= s.length()){
                break;
            }
            // 2. "ab"
            // 3. "aba"
            // 4. "abab"
            if (chars[i] != chars[end]){
                dp[i][end] = false;
            }else{
                dp[i][end] = end - i < 3 || dp[i+1][end-1];
            }
        }
    }
    return dp;
}

返回一个二维数组，代表了不同开始和结束的组合是否为回文子串

int maxLen = 0;
int start = 0;
for (int i = 0; i < dp.length; i++) {
    for (int j = 0; j < dp.length; j++) {
        if (dp[i][j]){
            if (j - i + 1> maxLen){
                maxLen = j - i + 1;
                start = i;
            }
        }
    }
}
System.out.println(s.substring(start, start + maxLen));

二、接雨水

public static int trap(int[] height){
    int len = height.length;
    if (len < 2) return 0;
    int[] left = new int[len];
    int[] right = new int[len];
    left[0] = height[0];
    right[len - 1] = height[len - 1];
    for (int i = 1; i < len; i++) {
        left[i] = Math.max(height[i], left[i-1]);
    }
    for (int i = len-2; i >= 0; i--){
        right[i] = Math.max(height[i], right[i+1]);
    }
    int ans = 0;
    for (int i = 0; i < len; i++) {
        ans += Math.min(left[i], right[i] - height[i]);
    }
    return ans;
}

三、正则匹配

public static boolean isMath(String s, String p){
    int m = s.length();
    int n = p.length();
    boolean[][] dp = new boolean[m+1][n+1];
    dp[0][0] = true;
    // 如何是开头为*，则可以当做字符，也可以不当做字符
    for (int i = 1; i <= n; i++) {
        if (p.charAt(i-1) == '*'){
            dp[0][i] = true;
        }else{
            break;
        }
    }
    // 如果为*，则可以是匹配这个字符，也可以是不匹配这个字符
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p.charAt(j - 1) == '*'){
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }else if (p.charAt(j - 1) == '?' || s.charAt(i - 1) == p.charAt(j - 1)){
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}