专栏首页小鹏的专栏data_structure_and_algorithm -- 如何找到字符串中最长回文子串: python & java实现

data_structure_and_algorithm -- 如何找到字符串中最长回文子串: python & java实现

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"

Output: "bb"

python实现:

def is_plalindrome(s):
    s_len = len(s)
    for i in range(s_len/2):
        if s[i] != s[s_len-i-1]:
            return False
    return True

def pre_handle_string(s):
    sb = '#'
    s_len = len(s)
    for i in range(s_len):
        sb = sb + s[i] + '#'
    return str(sb)

# 寻找最长回文字串
def find_longest_plalindrome_string(s):
    # 预处理字符串, 加 '#'
    ss = pre_handle_string(s)
    # 处理后的字符长度
    ss_len = len(ss)
    # 右边界
    right_side = 0
    # 右边界对应的回文串中心
    right_side_center = 0
    # 保存以每个字符为中心的回文长度一半(向下取正)
    half_len_arr = [0 for i in range(ss_len)]
    # 记录回文中心
    center = 0
    # 记录最长回文长度
    longest_half = 0

    for i in range (ss_len):
        # 是否需要中心扩展
        need_calc = True
        # 如果在右边界的覆盖之内
        if right_side > i:
            # 计算相对right_side_center的对称位置
            left_center = 2*right_side_center - i
            # 根据回文性质得出结论
            half_len_arr[i] = half_len_arr[left_center]
            # 如果超过了右边界,进行调整
            if i+half_len_arr[i] > right_side:
                half_len_arr[i] = right_side-i
            # 如果根据已知条件计算得出的最长回文小于右边界,则不需要扩展了
            if i+half_len_arr[left_center] < right_side:
                need_calc = False
        # 中心扩展
        if need_calc:
            while (i-1-half_len_arr[i]>=0) and (i+1+half_len_arr[i] < ss_len):
                if ss[i+1+half_len_arr[i]] == ss[i-1-half_len_arr[i]]:
                    half_len_arr[i] = half_len_arr[i]+1
                else:
                    break
            
            # 更新右边界及中心
            right_side = i + half_len_arr[i]
            right_side_center = i
            # 记录最长回文串
            if half_len_arr[i] > longest_half:
                center = i
                longest_half = half_len_arr[i]
    sb = ''
    # +2是因为去掉之间添加的#
    for i in range (center-longest_half+1,center+longest_half,2):
        sb = sb + ss[i]

    return str(sb)


if __name__ == '__main__':
    test_str = ["abcdcef",
            "adaelele",
            "cabadabae",
            "aaaabcdefgfedcbaa",
            "aaba",
            "aaaaaaaaa"]
    for per_str in test_str:
        print ("原字串 : %s", per_str)
        print ("最长回文串 : %s", find_longest_plalindrome_string(per_str))
    pass

java代码比较给力:

PlalindromeString.java

public class PlalindromeString {

    // 判断一个字符串是否回文,算法中用不到了
    @Deprecated
    private boolean isPlalindrome(String s) {
        int len = s.length();
        for(int i = 0; i < len / 2; i++) {
            if(s.charAt(i) != s.charAt(len - 1 - i)) {
                return false;
            }
        }
        return true;
    }

    // 预处理字符串,在两个字符之间加上#
    private String preHandleString(String s) {
        StringBuffer sb = new StringBuffer();
        int len = s.length();
        sb.append('#');
        for(int i = 0; i < len; i++) {
            sb.append(s.charAt(i));
            sb.append('#');
        }
        return sb.toString();
    }

    // 寻找最长回文字串
    public String findLongestPlalindromeString(String s) {
        // 先预处理字符串
        String str = preHandleString(s);
        // 处理后的字串长度
        int len = str.length();
        // 右边界
        int rightSide = 0;
        // 右边界对应的回文串中心
        int rightSideCenter = 0;
        // 保存以每个字符为中心的回文长度一半(向下取整)
        int[] halfLenArr = new int[len];
        // 记录回文中心
        int center = 0;
        // 记录最长回文长度
        int longestHalf = 0;
        for(int i = 0; i < len; i++) {
            // 是否需要中心扩展
            boolean needCalc = true;
            // 如果在右边界的覆盖之内
            if(rightSide > i) {
                // 计算相对rightSideCenter的对称位置
                int leftCenter = 2 * rightSideCenter - i;
                // 根据回文性质得到的结论
                halfLenArr[i] = halfLenArr[leftCenter];
                // 如果超过了右边界,进行调整
                if(i + halfLenArr[i] > rightSide) {
                    halfLenArr[i] = rightSide - i;
                }
                // 如果根据已知条件计算得出的最长回文小于右边界,则不需要扩展了
                if(i + halfLenArr[leftCenter] < rightSide) {
                    // 直接推出结论
                    needCalc = false;
                }
            }
            // 中心扩展
            if(needCalc) {
                while(i - 1 - halfLenArr[i] >= 0 && i + 1 + halfLenArr[i] < len) {
                    if(str.charAt(i + 1 + halfLenArr[i]) == str.charAt(i - 1 - halfLenArr[i])) {
                        halfLenArr[i]++;
                    } else {
                        break;
                    }
                }
                // 更新右边界及中心
                rightSide = i + halfLenArr[i];
                rightSideCenter = i;
                // 记录最长回文串
                if(halfLenArr[i] > longestHalf) {
                    center = i;
                    longestHalf = halfLenArr[i];
                }
            }
        }
        // 去掉之前添加的#
        StringBuffer sb = new StringBuffer();
        for(int i = center - longestHalf + 1; i <= center + longestHalf; i += 2) {
            sb.append(str.charAt(i));
        }
        return sb.toString();
    }

}

Main.java

public class Main {

    public static void main(String[] args) {

        PlalindromeString ps = new PlalindromeString();

        String[] testStrArr = new String[] {
            "abcdcef",
            "adaelele",
            "cabadabae",
            "aaaabcdefgfedcbaa",
            "aaba",
            "aaaaaaaaa"
        };

        for(String str : testStrArr) {
            System.out.println(String.format("原字串 : %s", str));
            System.out.println(String.format("最长回文串 : %s", ps.findLongestPlalindromeString(str)));
            System.out.println();
        }

    }

}

运行结果:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • tf22: ocr识别——不定长数字串识别

    上一篇: 身份证识别——生成身份证号和汉字 代码如下: #!/usr/bin/env python2 # -*- coding: utf-8 -*- """ t...

    MachineLP
  • 基于SIFT特征的图像检索 vs CNN

    下面简单的对比一下sift和cnn的检索结果:(基于此改进的版本好多:各种sift;cnn(vgg-fc3;vgg(resnet、inception等)-con...

    MachineLP
  • tf45:tensorflow计算图是如何做的?

    MachineLP的Github(欢迎follow):https://github.com/MachineLP

    MachineLP
  • 1074 宇宙无敌加法器 (20 分)

    地球人习惯使用十进制数,并且默认一个数字的每一位都是十进制的。而在 PAT 星人开挂的世界里,每个数字的每一位都是不同进制的,这种神奇的数字称为“PAT数”。每...

    可爱见见
  • [编程] C语言结构体指针作为函数参数

    结构体指针作为函数参数: 结构体变量名代表的是整个集合本身,作为函数参数时传递的整个集合,也就是所有成员,而不是像数组一样被编译器转换成一个指针。如果结构体成员...

    陶士涵
  • C#版[击败98.85%的提交] - Leetcode717. 1比特与2比特字符 - 题解

    在线提交: https://leetcode-cn.com/problems/1-bit-and-2-bit-characters/

    Enjoy233
  • grafana 介绍与安装、配置

    grafana 是一款采用 go 语言编写的开源应用,主要用于大规模指标数据的可视化展现,基于商业友好的 Apache License 2.0 开源协议。是网络...

    用户5760343
  • SPOJ8222 NSUBSTR - Substrings(后缀自动机)

    attack
  • 洛谷P3346 [ZJOI2015]诸神眷顾的幻想乡(广义后缀自动机)

    因为所有合法的答案一定是某个叶子节点为根的树上的一条链,因此这样可以统计出所有合法的答案

    attack
  • 洛谷P2759 奇怪的函数(log 二分)

    attack

扫码关注云+社区

领取腾讯云代金券