PHP之最长回文串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
来源:力扣(LeetCode)
class Solution {
/**
* @param String $s
* @return String
*/
function longestPalindrome($s) {
$s_len = strlen($s);
if ($s_len < 1) {
return ‘‘;
} elseif ($s_len <= 2) {
return $s{0} == $s{1} ? $s : $s{0};
}
$symbol = ‘#‘;
$s_with_symbol = "\$" . $symbol;
for ($i = 0; $i < $s_len; $i ++) {
$sub_s = $s{$i} . $symbol;
$s_with_symbol .= $sub_s;
}
$p = [];
$mx = 0;
$id = 0;
$resLen = 0;
$resCenter = 0;
$s_with_symbol_len = strlen($s_with_symbol);
for ($i = 1; $i < $s_with_symbol_len; $i ++) {
$p[$i] = $mx > $i ? min($p[2 * $id - $i], $mx - $i) : 1;
while ($s_with_symbol{$i + $p[$i]} == $s_with_symbol{$i - $p[$i]}) {
++ $p[$i];
if ($mx < $p[$i] + $i) {
$mx = $p[$i] + $i;
$id = $i;
}
if ($resLen < $p[$i]) {
$resLen = $p[$i];
$resCenter = $i;
}
}
}
return substr($s, ($resCenter - $resLen)/2, $resLen - 1);
}
}
相关推荐
amberom 2020-08-03
有梦就能实现 2020-06-10
poplpsure 2020-05-27
fujuan000 2020-04-30
Crazyshark 2019-06-25
知足者常乐 2019-09-02
有梦就能实现 2018-05-20
Crazyshark 2014-07-24
drise 2013-11-25
ahxxx 2019-07-01
spinachcqb 2019-06-28
技术渣 2016-10-07
会写code的凳子哥 2016-09-23
Phplayers 2019-06-28
wangdoudou0 2015-07-07
cxymds 2019-06-27
spinachcqb 2019-06-27
Cricket 2019-06-27