php 最长回文子串

php 最长回文子串最长回文子串由于case包含奇偶性,所以分两种情况讨论思路:找到以字符”x”为中心的最长回文子串从x的下标开始遍历,拆分为偶数对称情况和奇数对称情况 终止条件有2: 对称位置的字符不相同 循环右侧下标超出字符长度 结果:1364ms14.9MB主要难点是:计算下标代码:classSolution{/***@paramStr…

大家好,又见面了,我是你们的朋友全栈君。

最长回文子串

由于case包含奇偶性,所以分两种情况讨论

思路:找到以字符”x”为中心的最长回文子串

  1. 从x的下标开始遍历,拆分为偶数对称情况和奇数对称情况
  2. 终止条件有2:
    1. 对称位置的字符不相同
    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;
    }
}

 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/135660.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • igmp协议分析_协议分析

    igmp协议分析_协议分析IGMP协议。通过抓包详细分析了IGMP成员报告报文和IGMP离组报文。类型1字节最大响应时间1字节检验和2字节多播地址4字节类型11成员查询12成员报告(v1)16成员报告(v2)22成员报告(v3)17成员退出IGMP协议分析…

  • cas单点登录实现原理(用户登录测试用例)

    转载地址http://www.cnblogs.com/lihuidu/p/6495247.html1、基于Cookie的单点登录的回顾    基于Cookie的单点登录核心原理:   将用户名密码加密之后存于Cookie中,之后访问网站时在过滤器(filter)中校验用户权限,如果没有权限则从Cookie中取出用户名密码进行登录,让用户从某种意义上觉得只登录了一次。   该方式缺…

  • 安装win8、ubuntu双系统的过程

    弄了一个晚上,终于完成了,之前是用虚拟机的,但是觉得不带劲,并且折腾来时菜鸟变大神的捷径,虽然现在还一直在爬坑。继续奋斗吧…王小二首先是看ubuntu百度贴吧的安装帖子(http://tieb

    2021年12月20日
  • linux中find命令基本使用方法_find命令用法及参数

    linux中find命令基本使用方法_find命令用法及参数Linux系统find命令用法Linux查找命令find是Linux系统中最重要和最常用的命令之一,用于查找与指定参数条件匹配的文件及目录列表。find查找命令可以在各种条件下使用,我们可以通过权限,用户,组,文件类型,修改日期,大小等多种条件来查找文件。这里我会以实例的形式向大家说明find命令的具体用法。find命令的格式很简单,一般分成三个部分:1)find命令;2)搜索路径(目录可以写多个);3)表达式。对于find命令,最需要学习的是表达式这一段。表达式决定了我们要找的文件是什么属性的文件

  • 口罩、安全帽识别比赛踩坑记(一) 经验漫谈及随想

    口罩、安全帽识别比赛踩坑记(一) 经验漫谈及随想前言       因为疫情迎来的史无前例大假期,从开始理直气壮的天天划手机,到中间百无聊赖的躺尸,再到之后实在憋得慌,就想找点什么事搞一搞。恰好这时,一直关注的极视角联合Intel公司举办了一个对口罩和安全帽进行识别的比赛,能免费用一个月的云服务器对于我这还在用跑个Demo都能卡死的老爷机来说还是相当具有吸引力的。于是…

  • java inputstream和outputstream_string java

    java inputstream和outputstream_string javaInputStream读取流有三个方法,分别为read(),read(byte[]b),read(byte[]b,intoff,intlen)。其中read()方法是一次读取一个字节,效率是非常低的。所以最好是使用后面两个方法。/***读取流**@paraminStream*@return字节数组*@throwsException*/publicstaticbyte[…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号