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)


相关推荐

  • 【Android布局】在程序中设置android gravity 和 android layout Gravity属性

    【Android布局】在程序中设置android gravity 和 android layout Gravity属性【Android布局】在程序中设置androidgravity和androidlayoutGravity属性

  • MySQL中特别实用的几种SQL语句送给大家[通俗易懂]

    MySQL中特别实用的几种SQL语句送给大家[通俗易懂]在写SQL时,经常灵活运用一些SQL语句编写的技巧,可以大大简化程序逻辑。减少程序与数据库的交互次数,有利于数据库高可用性,同时也能显得你的SQL很牛B,让同事们眼前一亮。目录实用的SQL1.插入或替换2.插入或更新3.插入或忽略4.SQL中的if-else判断语句5.指定数据快照或备份6.写入查询结果集7.强制使用指定索引心得体会:高能预警,这是一篇干货满满的MySQL技术文章,总有一天,你必然会用到,记得收藏!–来自一位被技术经理毒打多年的程序员的忠.

  • 2020年读书随笔一篇_2020年教师读书笔记

    2020年读书随笔一篇_2020年教师读书笔记Note:以下markdown格式文本由json2md自动转换生成,可参考JSON转Markdown:我把阅读数据从MongoDB中导出转换为.md了了解具体的转换过程。面纱作者:毛姆[英]ISBN:9787210082835出版社:江西人民出版社出版日期:2016-04-01图书标签:毛姆,小说,英国文学,英国,外国文学豆瓣地址:https://book.douban.com/subject/26757680/阅读日期:2020-01-19读书笔记威廉·萨默塞特·毛姆(

  • plsql developer 使用技巧[通俗易懂]

    plsql developer 使用技巧[通俗易懂] Oracle数据库相信已成为很多企业构建自身关键业务的重要后台支撑,也是众多开发人员常常采用的后台。但Oracle自己提供的一套客户端工具不是很好用,极大的影响了工作效率,幸好现在有了PL/SQLDeveloper这款工具。现在越来越多的开发人员成了它的忠实fans。本文就是立足于实用的基础上,总结了了改工具的常用技巧:   1.记住登陆密码   为了工作方便希望PL/SQLDe…

  • H265文件_h265转码工具

    H265文件_h265转码工具一、H264格式RBSP=SODB+RBSPtrailingbitsNALU=NALheader(1byte)+RBSPH.264=StartCodePrefix(3bytes)+NALU+StartCodePrefix(3bytes)+NALU+…H.264从层次来看分为两层:视频编码层(VCL,VideoCo…

  • Java解析XML文件的方式

    Java解析XML文件的方式在项目里,我们往往会把一些配置信息放到xml文件里,或者各部门间会通过xml文件来交换业务数据,所以有时候我们会遇到“解析xml文件”的需求。一般来讲,有基于DOM树和SAX的两种解析xml文件的方式,在这部分里,将分别给大家演示通过这两种方式解析xml文件的一般步骤。1XML的文件格式XML是可扩展标记语言(ExtensibleMarkupLanguage)的缩写,…

发表回复

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

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