ahxxx 2019-11-03
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。
示例 2:
输入: "cbbd" 输出: "bb"
这个就不用多解释了
class Solution { /** * 法一: * @param String $s * @return String */ function longestPalindrome($s) { $len = strlen($s); $tmps = ''; $max = 0; for($i=0 ; $i<$len; $i++){ //起始下标 for($j=$i+1; $j<=$len;$j++){ //长度 if($this->isPalindrome(substr($s,$i,$j)) && $j > $max){ $tmps = substr($s,$i,$j); $max = $j; } } } return $tmps; } function isPalindrome($subs){ $len = strlen($subs); for($i=0; $i<(int)($len/2); $i++){ if($subs[$i] != $subs[$len-$i-1]){ return false; } } return true; } }
思路:就是把字符串反转过来,例如 s=‘ababc’,反正s‘=’cbaba‘,两个字符串左右重合,得出最长的子串就是答案,也就是bab(或aba)。但是有可能会出现==特例(如:S = abc435cba,S' = abc534cba)==,重合,子串为abc。不符合条件,需要加判断
class Solution2 { /** * @param String $s * @return String */ function longestPalindrome($s) { $len = strlen($s); if($len == ''){ return $s; } $origin = $s; $reverse = strrev($s); $arr = []; $maxLen = 0; $maxStart = 0; for($i=0; $i<$len; $i++){//原始字符串下标 for($j=0; $j<$len; $j++){ //倒置后字符串下标 if($origin[$i] == $reverse[$j]){ if($i == 0 || $j ==0){ $arr[$i][$j] = 1; }else{ //状态转移方程 $arr[$i][$j] = $arr[$i-1][$j-1] + 1; } /** * 用来规避特殊情况 * 如:S = abc435cba,S' = abc534cba * 不特殊处理,abc 会被判断为最小回文子串 * 解:判断倒置前的子串下标,是否符合条件 */ if($arr[$i][$j] > $maxLen){ $beforeJ = $len - $j - 1; if($beforeJ + $arr[$i][$j] -1 == $i){ $maxLen = $arr[$i][$j]; $maxStart = $i; } } }else{ $arr[$i][$j] = 0; } } } echo substr($s,$maxStart-$maxLen+1,$maxLen); } }
把每个字母当成回文串的中心。考虑两种情况,长度为奇数和偶数
class Solution3 { /** * @param String $s * @return String */ function longestPalindrome($s) { $n = strlen($s); if($n == ''){ return $s; } $start = 0; $maxlen = 0; for($i=0; $i<$n; $i++){ $len1 = $this->isPalindrome($s,$i,$i);//奇数 $len2 = $this->isPalindrome($s,$i,$i+1);//偶数 $len = max($len1,$len2); if($len > $maxlen){ $start = $i - ($len-1)/2; $maxlen = $len; } } return substr($s,$start,$len) ; } function expend($str,$i,$j){ $n = strlen($str); $l = $i; $r = $j; while($l>=0 && $r<$n && $str[$l] == $str[$r]){ $l-- ; $r++ ; } return $r-$l-1; } }
重新组合字符串,将其变为奇数个。充分的利用回文串的对称性质,
class Solution4 { /** * @param String $s * @return String */ function longestPalindrome($s) { $T = $this->malache($s); $n = strlen($T); $C = $R = 0; $p = []; for($i=1; $i<$n-1; $i++){ $i_mirror = $C*2 - $i; if($R>$i){ $p[$i] = min($R-$i,$p[$i_mirror]); }else{ $p[$i] = 0; } while(($T[$i-1-$p[$i]]) == ($T[$i+1+$p[$i]]) ){ $p[$i]++; } if($i + $p[$i] > $R) { $C = $i; $R = $i + $p[$i]; } } $maxLen = 0; $centerIndex = 0; for ($i=1; $i<$n-1;$i++ ){ if($p[$i] > $maxLen){ $maxLen = $p[$i]; $centerIndex = $i; } } $start = ($centerIndex-$maxLen)/2; echo substr($s,$start,$maxLen); } function malache($str){ $n = strlen($str); if(!$str){ return "^$"; } $ret = '^'; for($i=0; $i<$n; $i++){ $ret .= '#'.$str[$i]; } $ret .= "#$"; return $ret; } }