go 刷算法第二题——最长回文子串

本文主要是介绍go 刷算法第二题——最长回文子串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。

给定字符串A以及它的长度n，请返回最长回文子串的长度。

示例1

输入："abc1234321ab",12
返回值：7

思路： 穷举所有节点的方案。
满足条件时，存在以下两种情况

1. index节点为对称轴节点 [...,1,2,1,...]
2. index节点为对称轴左边第一个节点，对称轴不在节点上 [...,1,1,...]

package main
 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param A string字符串
 * @param n int整型
 * @return int整型
*/
// 最长回文子串
func getLongestPalindrome(A string, n int) int {
    if n < 2 {
        return 1
    }
    maxLen := 0
    runes := []rune(A)
    for i := 0; i < n; i++ {
        for j := 0; j < i; j++ {
            // 奇  aba
            // 假设当前位置满足，那么必须要长度大于已经得到的最大长度才进行赋值
            // 切片不能越界
            // 比较当前位置两边的等长切片是否满足对称数组
            if maxLen < 2*(i-j)+1 && 2*i-j+1 <= n && isT(runes[j:i], runes[i+1:2*i-j+1]) {
                maxLen = 2*(i-j) + 1
            }
            // 偶  abba
            if maxLen < 2*(i-j) && 2*i-j <= n && isT(runes[j:i], runes[i:2*i-j]) {
                maxLen = 2 * (i - j)
            }
        }
    }
    return maxLen
}
 
// a、b是否为对称数组，[1,2,3]与[3,2,1]对称
func isT(a []rune, b []rune) bool {
    arrLength := len(a)
    for i, j := 0, arrLength-1; i < arrLength; i, j = i+1, j-1 {
        if a[i] != b[j] {
            return false
        }
    }
    return true
}

这篇关于go 刷算法第二题——最长回文子串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！