聊聊算法——回文字符串

我这天天写核心业务的人，都没用什么算法啊！其实算法无处不在，栈队列树链表都包含算法思想，算法并不是单纯指用代码解决那些深奥难懂的数学逻辑问题，而是代码中的普适化思维。并且算法也不可怕，是基本功，就像足球中的体能训练，微软谷歌，想不想去？他们都是用算法来伺候上门人的，所以还是别太片面地看待问题。算法也是非常讲究的，稍有破绽，失之千里。熟悉各种框架各种源码，不如下笔写算法！因为框架是「用」，算法是「想」。今天来分析下回文字符串的解法。

「准备」

Idea2019.03/Gradle6.0.1/Maven3.6.3/JDK11.0.4

「难度」新手-- 战士 --老兵--大师

「目标」

1.查找字符串的最长回文子串算法

1 需求

找回文是很常见的一种场景，所以拿来做个典型。所谓回文，即左右对称的字符串，如“ABCBA”，它有三种解法，我这里只说两种：「中心扩展法」和「动态规划」，还有个Manacher 算法，此文略！

2 中心扩展法

「思路：既然回文是对称的，肯定有个中心，如从中心开始向两个方向同步扩展，直到遇到不同字符，即为最长回文子串。」

代码(Java版)：

public class N005 {
    public static void main(String[] args) {
        String s = "DECCED";
        System.out.println(sub(s));
    }
    /** 中心扩展 因扩展有两种可能 一是ABA型 二是ABBA型，故可以写一个公用的扩展函数expand()*/
    private static String sub(String s){
        int start = 0, end = 0;
        for (int i = 0; i < s.length(); i++) {
            // ABBA型
            int len1 = expand(s,i,i + 1);
            // ABA型
            int len2 = expand(s,i,i );
            int len = Math.max(len1,len2);
            // 只保留最大的子串
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        return s.substring(start,end + 1);
    }

    private static int expand(String s,int left,int right){
        int l = left;
        int r = right;
        while (l >= 0 && r < s.length() && s.charAt(l)==s.charAt(r)){
            l--;
            r++;
        }
        return r - l - 1;
    }
}

以上代码解析：

1. 回文对称有两种，一是”ABA”型，另一种是”ABBA”型，for循环中将字符串每个字符都假设为对称中心，使用两种类型的假设来左右扩展，并保存最大回文信息；
2. 为啥独立出来一个expand函数？因为对称有两种类型，写个函数来复用，代码更简洁；
3. expand函数的作用是获得回文的长度，比如”ABA”返回3，”ABBA”则返回4 ，两个下标差再减去 1 ，要注意的细节是这两个指针的最终位置，如下图，”ABA”型(上)，”ABBA”型如 (上)：

1. 关于代码中start和end 变量的计算：

• start=i-(len-1)/2，考虑上面两种类型的情况，按上面图例来说，i=2，start结果为 0 和 -0.5，但 (int) 0 和 (int) -0.5 都等于 0 ；
• end=i+len/2，同理，按上面图例来说，i=2，end结果为 4.5 和 5，(int) 4.5 和 (int) 5 等于 4 和 5 ；

使用这样的写法，虽然有点绕，主要是综合了两种类型的可能结果，分开写也可有其他形式。

1. 最后的细节就是subString方法，“ABCDE”.subString(0,5) 输出才是“ABCDE”。

3 动态规划法

我在前篇文章已经专门聊了「动态规划」，虽然动态规划严格讲是用于解决阶段决策问题的，但其核心思想(类似数学归纳法)也可用于其他场景，使用的就是状态转移方程。动态规划一定会使用dpTable来记录中间结果。

「思路：如果一个字符串是回文串，那么去掉首尾字符的子串也肯定是回文串，反过来想，如果子串 sub[i+1,j-1] 是回文串，只需要看 i 和 j 位置的字符是否相同，即可判断sub[i,j] 是否属于回文串。」

因为有 i 和 j ，我们使用一个二维数组做dpTable，如果定义dp[i][j]为位置 i 到 j的子串(包含首尾字符)是否为回文串，按照思路即可写出状态转移方程(Λ意为and)：

dp[i][j] = dp[i+1][j-1] Λ (char[i] == char[j])

那么这个dpTable 的对角线都是 true，因为 i = j 时，只有单个字符，同时，因为是从i 到 j 的子串，可以肯定 i < j，故只需计算dpTable右上部分：

于是可以先写一个初始版本(Java)：

private String sub2(String s){
    int len = s.length();
    boolean[][] dp = new boolean[len][len];
    // 初始化dp表的部分值
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    //
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (s.charAt(i) != s.charAt(j)){
                dp[i][j] = false;
            }else {
                dp[i][j] = dp[i + 1][j - 1];
            }
        }
    }
    // 记录回文串的开始位置和长度
    int start = 0;
    int length = 0;
    return s.substring(start,length);
}

再考虑边界情况，在char[i] == char[j] 时：

即子串subStr(i+1,j-1)长度无法构成子串，长度小于2，(j-1)-(i-1)+1<2，简化为 j-i<3 ，等价于subStr(i,j)长度为 2 或 3：

• 如果子串subStr(i+1,j-1)是空，那么subStr(i,j)是回文串；
• 如果子串subStr(i+1,j-1)只有一个字符，显然一个字符是回文串，那么subStr(i,j)是回文串；

补充边界后 ：

private static String sub2(String s){
    int len = s.length();
    boolean[][] dp = new boolean[len][len];
    // 记录回文串的开始位置和长度
    int start = 0;
    int length = 0;
    // 初始化dp表的部分值
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    //
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (s.charAt(i) != s.charAt(j)){
                dp[i][j] = false;
            }else {
                if (j - i < 3){
                    dp[i][j] = true;
                }else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }
            // 记录最长回文信息
            if (dp[i][j] && j-i+1 > length){
                start = i;
                length = j - i + 1;
            }
        }
    }
    return s.substring(start,length);
}

以上代码分析：1 双重for循环，计算出dpTable中的值；2 最长回文信息只需记录起点和长度即可，当然也可记录起止位置，效果一样; 3 s.charAt(i) != s.charAt(j) 且 subStr(i,j)长度大于3 时，才会使用状态转移方程！

至此，寻找回文字符串算法你学会了吗？

「全文完！」

我近期其他文章：

• 1  聊聊算法--堆的构建和调整
• 2  Dubbo学习系列之十九（Apollo配置中心）
• 3  聊聊算法——二分查找算法深度分析
• 4  DevOps系列——Jenkins/Gitlab自动打包部署
• 5  DevOps系列——Jenkins私服

只写原创，敬请关注