题解 | #密码截取#

华为-密码截取（回文串）

• 华为-密码截取（回文串） | 牛客网

采用动态规划思想求解，记 d[i][j] 表示索引区间 [i,j] 的字符串是否可以构成回文串

1. 若 i=j，则一定有 dp[i][j] = true
2. 若 s[i] = s[j] 并且 (i+1) <= (j-1)，则有 dp[i][j] = dp[i+1][j-1]。该状态转移方程中，i 逐渐变大，j 逐渐变小，所以在循环过程中，要「反向迭代 i，正向迭代 j」，即保证计算 dp[i][j] 状态时，dp[i+1][j-1] 已经计算出来了。
3. 若 s[i] = s[j] 但不满足 (i+1) <= (j-1)时，即 i < j <= i+2，这可以分为两种情况
   • j=i+1，此时 s[i] = s[j]，字符串为 AA，所以一定有 dp[i][j] = true
   • j=i+2，此时 s[i] = s[j]，字符串为 AXA，所以一定有 dp[i][j] = true
4. 边界条件为 dp[i][i] = true

动态规划

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String str = in.next();
            int len = str.length();
            if(len == 1){
                System.out.println(1);
                return;
            }
            
            boolean[][] dp = new boolean[len][len];
            //边界条件
            for(int i=0;i<len;i++){
                dp[i][i] = true;
            }
            int maxLength = 1; //初始值是1 不是0
            //正向迭代j  反向迭代i
            for(int i=len-1;i>=0;i--){
                for(int j=i;j<len;j++){ //注意从j=i开始循环
                    if(i == j){   //line 1
                        dp[i][j] = true;
                    } else if(str.charAt(i) ==  str.charAt(j)){
                        if((i+1) <= (j-1)){
                            dp[i][j] = dp[i+1][j-1];
                        } else {
                           //(i+1) >= (j-1)
                           //再根据循环条件知道一定有 j>i (j=i的情况，已经在line 1 处排除)
                           //故有 i < j <= i+2，此时 j 一共有两种取值
                           // 1. j=i+1，此时s[i] = s[j]，字符串为AA，所以一定有  dp[i][j] = true;
                           // 2. j=i+2，此时s[i] = s[j]，字符串为AXA，所以一定有  dp[i][j] = true;
                           dp[i][j] = true;
                        
                        }
                    }
                    //更新最大长度
                    if(dp[i][j]){
                        maxLength = Math.max(maxLength,j-i+1);
                    }
                }
            }
            
            System.out.println(maxLength);
            
        }
        in.close();
    }
}

在这里记录一个编写代码时遇到的低级错误，错误版本如下。

//条件1 (i+1) <= (j-1)
//条件2 dp[i+1][j-1]
if((i+1) <= (j-1) && dp[i+1][j-1]){
    dp[i][j] = true;  //line A
} else {
    dp[i][j] = true; //line B
}

上述版本是错误逻辑，该错误版本中，当条件 1 和条件 2，同时满足时，执行 line A。若不同时满足，执行 line B。

正确的逻辑时若满足条件 1，但不满足 条件 2 时，不应该执行 line B。 正确的版本如下。

//条件1 (i+1) <= (j-1)

if((i+1) <= (j-1)){
    dp[i][j] = dp[i+1][j-1];  //line A
} else {
    dp[i][j] = true; //line B
}