动态规划+中心扩展重新理解寻找最长回文子串

た入场券 2023-05-21 07:24 7阅读 0赞

问题描述[https://leetcode-cn.com/problems/longest-palindromic-substring/][https_leetcode-cn.com_problems_longest-palindromic-substring]

### 动态规划的四个过程 ###

1.划分状态，即划分子问题。

如果一个字符串是回文字符串，那么它肯定满足1.两端的两个字符相等 2.除去两端两个字符剩下的还是回文字符串。以此往字符串串中心位置类推都满足这个规律。那可以找任意一个字符作为中心点，从中心点开始向两边扩散，判断是否满足回文。

2.状态表示，即如何让计算机理解子问题。

子字符串的起始位置和截止位置，可以类比到二维数组的横纵坐标，即用arrs\[start\]\[end\]表示str.substring(start, end+1)子串，数组的值设置为boolean，表示这一段是不是回文字符串。这样自底向上计算的时候，就可以利用已经计算过的状态。

3.状态转移，即父问题是如何由子问题推导出来的。

根据1的划分状态，一个字符串是不是回文，可以表示为

arrs\[start\]\[end\] = arrs\[start+1\]\[end-1\] && str.charAt(start)==str.charAt(end)

4.确定边界。

*  如果字符串长度为1，默认就是回文
 *  如果字符串长度为2，满足两个字符相等是回文
 *  如果字符串长度为3，满足第一个和第三个字符相等是回文，第二个作为中心是什么无所谓了
 *  如果字符串长度>3，满足除最两端两个字符外的内部字符是回文，并且第一个和最后一个字符相等

### 代码 ###

以l表示子串的起始位置，r表示子串的截止位置，把所有子串遍历一遍，判读是不是回文，并以一个变量记录最长回文的长度，如果后续有更长的回文时，更新这个值。写出来的代码如下所示

private static void subStr() { 
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int length = s.length();
        // 边界：如果字符串长度为1，默认就是回文
        if (s.length() == 1) { 
            System.out.println("longest :" + s);
            return;
        }
        // start、end记录回文子串的起止位置，manLen记录回文的最大长度
        int start = 0;
        int end = 0;
        int maxLen = 0;
        // 二维数组把自底向上的判断结果暂存，用于状态转移方程的推导
        boolean[][] arrs = new boolean[length][length];
        // 结尾的位置从1到最后一位
        for (int r = 1; r < length; r++) { 
            // 起始的位置从0到结尾位置之前（< r）
            for (int l = 0; l < r; l++) { 
                // 长度为2，中心位置是两个相同的字符
                if (r - l == 1 && s.charAt(l) == s.charAt(r)) { 
                    arrs[l][r] = true;
                    if (r - l + 1 > maxLen) { 
                        start = l;
                        end = r;
                        maxLen = (r - l) * 2;
                    }
                    // 长度为3，中心位置是一个字符，中心两侧的两个字符相等
                } else if (r - l == 2 && s.charAt(l) == s.charAt(r)) { 
                    arrs[l][r] = true;
                    if (r - l + 1 > maxLen) { 
                        start = l;
                        end = r;
                        maxLen = (r - l) * 2;
                    }
                    //长度超过3，满足状态转移方程
                } else if (arrs[l+1][r-1] && s.charAt(l) == s.charAt(r)) { 
                    arrs[l][r] = true;
                    if (r - l + 1 > maxLen) { 
                        start = l;
                        end = r;
                        maxLen = (r - l) * 2;
                    }
                }
            }
        }
        System.out.println("longest :" + s.substring(start, end + 1)); // substring不包括endIndex，end + 1
    }

三种分支判断合并以后

private static void subStr2() { 
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        int length = s.length();
        // 边界：如果字符串长度为1，默认就是回文
        if (s.length() == 1) { 
            System.out.println("longest :" + s);
            return;
        }
        // start、end记录回文子串的起止位置，manLen记录回文的最大长度
        int start = 0;
        int end = 0;
        int maxLen = 0;
        // 二维数组把自底向上的判断结果暂存，用于状态转移方程的推导
        boolean[][] arrs = new boolean[length][length];
        for (int r = 1; r < length; r++) {  // 结尾的位置从1到最后一位
            for (int l = 0; l < r; l++) {  // 起始的位置从0到结尾位置之前（< r）
                // ||的优先级低于&&，前半段加括号
                if ((arrs[l+1][r-1] || r - l <= 2) && s.charAt(l) == s.charAt(r)) { 
                    arrs[l][r] = true;
                    if (r - l + 1 > maxLen) { 
                        start = l;
                        end = r;
                        maxLen = r - l + 1;
                    }
                }
            }
        }
        // substring不包括endIndex，end + 1
        System.out.println("longest :" + s.substring(start, end + 1));
    }

[https_leetcode-cn.com_problems_longest-palindromic-substring]: https://leetcode-cn.com/problems/longest-palindromic-substring/