• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

聊聊算法——回文字符串

开发技术 开发技术 3周前 (09-06) 22次浏览

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

「准备」

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私服

只写原创,敬请关注 

聊聊算法——回文字符串

 


喜欢 (0)