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"
<?php
/**
* Created by PhpStorm.
* User: zhanglingyu
* Date: 2019-04-02
* Time: 09:45
*/
// 40ms
class Solution
{
/**
* @param String $s
* @return String
*/
function longestPalindrome($s)
{
$maxLengthQuanJu = 1;
$maxStr = '';
$length = strlen($s);
if ($length == 0) {
return '';
} else {
for ($i = 0; $i < $length; $i++) {
for ($maxLength = $maxLengthQuanJu; $maxLength <= $length; $maxLength++) {
if ($maxLength % 2 == 0) {
//偶数
$start = $i - ($maxLength / 2);
} else {
//奇数
$start = $i - (($maxLength - 1) / 2);
}
if ($start < 0) {
break;
}
$end = $start + $maxLength;
if ($end > $length) {
break;
}
$lsStr = substr($s, $start, $maxLength);
if ($lsStr == strrev($lsStr)) {
$maxStr = $lsStr;
$maxLengthQuanJu = $maxLength;
} else {
//不符合要求
if ($maxLengthQuanJu < ($maxLength - 1)) {
break;
} else {
continue;
}
}
}
}
}
return $maxStr;
}
}
class Test extends \PHPUnit\Framework\TestCase
{
/** @test */
public function testSolution()
{
$solution = new Solution();
$s1 = 'babad';
$this->assertEquals($solution->longestPalindrome($s1), 'aba');
$s2 = 'cbbd';
$this->assertEquals($solution->longestPalindrome($s2), 'bb');
}
}
// 8ms
func longestPalindrome(s string) string {
if len(s) < 2 {
return s
}
max := string(s[0])
for i:=0;i<len(s);i++ {
max = checkPalindrome(s, i, i, max)
max = checkPalindrome(s, i, i+1, max)
}
return max
}
func checkPalindrome(s string, i int, j int, max string) string {
leng := len(s)
var sub string
for i>=0 && j<=(leng - 1) && s[i] == s[j] {
sub = s[i:j+1]
i--
j++
}
if len(max) < len(sub) {
max = sub
}
return max
}
// 0ms 目瞪口呆
type palin struct {
left, right int
}
func longestPalindrome(s string) string {
max := &palin{}
maxSize := 0
l := len(s)
// Edge cases
if l == 0 || l == 1 {
return s
}
// Check if whole string is palindrome
isPalindrome := true
for i, j := 0, l-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
isPalindrome = false
break
}
}
if isPalindrome {
return s
}
// Do it the hard way
for i := 0; i < l; i++ {
// Add consecutive equals
if i < l-1 && s[i] == s[i+1] {
p := &palin{
left: i,
right: i + 1,
}
p, size := getPalin(s, l, p)
if size > maxSize {
maxSize = size
max = p
}
}
// Add surrounding equals
if i > 0 && i < l-1 && s[i-1] == s[i+1] {
p := &palin{
left: i - 1,
right: i + 1,
}
p, size := getPalin(s, l, p)
if size > maxSize {
maxSize = size
max = p
}
}
}
return s[max.left : max.right+1]
}
func getPalin(s string, l int, p *palin) (*palin, int) {
j := 1
for p.left-j >= 0 && p.right+j < l && s[p.left-j] == s[p.right+j] {
j++
}
p.left = p.left - j + 1
p.right = p.right + j - 1
return p, p.right - p.left + 1
}
方法一一般是自己实现的方法，其他方式是在discuss中查找的更为优秀的方法，用作学习和借鉴。