php 最长回文子串
PHP 最长 回文 子串
2023-06-13 09:11:56 时间
大家好,又见面了,我是你们的朋友全栈君。
由于case包含奇偶性,所以分两种情况讨论
思路:找到以字符”x”为中心的最长回文子串
- 从x的下标开始遍历,拆分为偶数对称情况和奇数对称情况
- 终止条件有2:
- 对称位置的字符不相同
- 循环右侧下标超出字符长度
结果:1364 ms 14.9 MB
主要难点是:计算下标
代码:
class Solution
{
/**
* @param String $s
* @return String
*/
function longestPalindrome($s)
{
$sArray = str_split($s, 1);
$length1 = 1;
$length2 = 1;
$max = 1;
$maxS = $sArray[0];
$subS1 = $sArray[0];
$subS2 = $sArray[0];
$sLength = sizeof($sArray);
for ($i = 0; $i < $sLength; $i++) {
$bool1 = false;
$bool2 = false;
for ($j = $i; $j >= 0; $j--) {
if ($sLength > 2) {
// 奇数情况
if ($sArray[$i - 1] == $sArray[$i + 1] && !$bool2 && (2 * $i - $j) <= $sLength - 1) {
$length2 = 2 * ($i - $j) + 1;
$subS2 = substr($s, $j, $length2);
if ($sArray[$j] != $sArray[2 * $i - $j]) {
$length2 = 2 * ($i - $j) - 1;
$subS2 = substr($s, $j + 1, $length2);
$bool2 = true;
}
}
}
// 偶数情况
if ($sArray[$i] == $sArray[$i + 1] && !$bool1 && (2 * $i - $j + 1) <= $sLength - 1) {
$length1 = 2 * ($i - $j + 1);
$subS1 = substr($s, $j , $length1);
if ($sArray[$j] != $sArray[2 * $i - $j + 1]) {
$length1 = 2 * ($i - $j);
$subS1 = substr($s, $j + 1, $length1);
$bool1 = true;
}
}
if ($bool1 && $bool2) {
break;
}
}
$length = $length1 > $length2 ? $length1 : $length2;
$subS = $length1 > $length2 ? $subS1 : $subS2;
if ($length > $max) {
$maxS = $subS;
$max = $length;
}
if (($sLength - $i - 1) * 2 <= $max) {
break;
}
}
return $maxS;
}
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/135660.html原文链接:https://javaforall.cn
相关文章
- Php面试问题_php面试常问面试题
- 十天学会PHP_十天学会php教程
- 【笔记php】如何使用PHP从JSON提取数据?
- PHP异步MySQL:提升网站性能的新方案(php异步mysql)
- PHP实现查询两个数组中不同元素的方法详解编程语言
- 在Linux上快速搭建PHP开发环境(linux搭建php环境)
- MySQL验证:PHP实现细节(php验证mysql)
- MySQL连接池:PHP提供的快速访问方式(mysql连接池php)
- 让Linux帮助启动PHP服务(linux启动php)
- 如何在Linux下顺利安装PHP?(在linux下安装php)
- mysql线程技术驱动PHP程序优化(mysql线程php)
- 使用PHP和MSSQL搭建技术论坛(php mssql 论坛)
- Phpbean路由转发的php代码
- 创建数据库php代码用PHP写出自己的BLOG系统
- php在文件指定行插入数据的代码
- PHP学习笔记之二php入门知识
- php基础学习之变量的使用
- PHP和Mysqlweb应用开发核心技术第1部分Php基础-1开始了解php
- 调试一段PHP程序时遇到的三个问题
- php模拟ping命令(phpexec函数的使用方法)
- php对二维数组按指定键值key排序示例代码
- PHP框架Swoole定时器Timer特性分析
- php实现的Captcha验证码类实例