嗨客网搜索
最长回文子串

描述

leetcode 官方第 5 题,给你一个字符串 s,找到 s 中最长的回文子串。

示例 1:

输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。

示例 2:

输入:s = "cbbd" 输出:"bb"

示例3:

输入:s = "a" 输出:"a"

示例4:

输入:s = "ac" 输出:"a"

提示:

  1. 1 <= s.length <= 1000
  2. s 仅由数字和英文字母(大写和/或小写)组成

思路

这题我们这里就简单粗暴的使用暴力计算的方法来实现,使用双重循环计算使用字符串的情况,并判断每一个字符串是否是回文字符串,如果是,并且长度大于当前最长回文字符串的长度,那么就保存结果。

判断是否是回文字符串,思想是使用两个指针分别指向字符串开始和结束,然后判断是否相等,如果相等,则继续左指针右移,右指针左移,如果不相等了,则表明不是回文字符串。如果相遇了还是相等,那说明是回文字符串。

比如,以我们示例一中的字符串 babad 为例,开始左右指针如下:

29_最长回文子串.png

此时,我们直接判断 pLeft 指针指向的字符与 pRight 指向的字符不相等,因此,直接就返回不是回文字符串。现在,我们判断一个是回文字符串的,如下:

30_最长回文子串.png

我们看到,此时 pLeft 指针指向的元素与 pRight 指针指向的元素相等,那么此时,我们继续右移 pLeft 指针,左移 pRight 指针,如下图:

31_最长回文子串.png

我们看到,此时 pLeft 指针与 pRight 指针指向的元素还是相等的,因此,我们继续移动指针,如下图:

32_最长回文子串.png

我们看到,此时 pLeft 指针与 pRight 指针已经重合了,因此,循环结束,即该字符串是回文字符串。

代码具体实现

Java语言版本

class Solution { public String longestPalindrome(String s) { int cnt = s.length(); String result = ""; //保存当前的最长子串的长度 int maxlen = 0; //暴力循环 for (int i = 0; i < cnt; i++){ //内存循环从外层循环的下一个索引开始 for (int j = i+1; j <= cnt; j++){ //如果是回文,并且当前长度大于了最大长度,则赋值并更新 if (isPalindromeStr(s.substring(i, j)) && j - i > maxlen){ result = s.substring(i, j); maxlen = j - i; } } } return result; } //判断是否是回文字符串,思想是使用两个指针分别指向字符串开始和结束,然后判断是否相等 //如果相等,则继续左指针右移,右指针左移 //如果不相等了,则表明不是回文字符串 //如果相遇了还是相等,那说明是回文字符串 public boolean isPalindromeStr(String str){ //左指针 int left = 0; //右指针 int right = str.length()-1; //循环的结束条件是左右指针重合 while(left < right){ //如果不相等了,则不是回文字符串,直接返回 if (str.charAt(left) != str.charAt(right)){ return false; } //左指针右移 left++; //右指针左移 right--; } //左右指针相遇了,还是相等,则表明是回文 return true; } }

Go语言版本

func longestPalindrome(s string) string { var( cnt = len(s) result = "" //保存当前的最长子串的长度 maxlen = 0 ) //暴力循环 for i := 0; i < cnt; i++{ //内存循环从外层循环的下一个索引开始 for j := i+1; j <= cnt; j++{ if isPalindromeStr(s[i:j]){ //如果是回文,并且当前长度大于了最大长度,则赋值并更新 if j - i > maxlen{ result = s[i:j] maxlen = j - i } } } } return result } //判断是否是回文字符串,思想是使用两个指针分别指向字符串开始和结束,然后判断是否相等 //如果相等,则继续左指针右移,右指针左移 //如果不相等了,则表明不是回文字符串 //如果相遇了还是相等,那说明是回文字符串 func isPalindromeStr(str string)(isPalindrome bool){ var( //左指针 left = 0 //右指针 right = len(str)-1 ) //循环的结束条件是左右指针重合 for left < right{ //如果不相等了,则不是回文字符串,直接返回 if str[left] != str[right]{ return } //左指针右移 left++ //右指针左移 right-- } //左右指针相遇了,还是相等,则表明是回文 isPalindrome = true return }

赞助商链接:


嗨客网顶部