首页 > 作文

Leetcode 5. 最长回文子串

更新时间:2023-04-08 13:26:34 阅读: 评论:0

题目要求

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
(具体要求请看)

解题思路

参考了各路大神的解题思路,就这种我感觉比较容易理解一点,所以就采用了中心扩展算法,等我再好好看看马拉车算法再和大家分享吧。
首先要了解回文的特点,它是关于中心对称的,这样的对称分为两种情况,一种的长度为奇数的字符串,一种是长度为偶数的字符串,根据这个特点,就可以分别比较中心两侧对应的字符,通过判断两侧对应字符是否相同来得出当前判断的子串是否为回文,代码如下:

代码

class solution {    protected $len    = 0;      // 字符串长度    protected $start  = 0;      // 起始位置    protected $length = 0;      // 截取长度    /**     * @param string $s     * @return string     */    public function longestpalindrome($s) {        $this->len = strlen($s);        for ($i = 0; $i < $this->len; $i++) {            // 如果起始位置 + 截取长度 = 字符串长度,就不需要继续循环下去幼儿园教师演讲稿,因为可以确定当前长度是云购最长的            if ($this->start + $this->length >= $this->len) break;            $this->expandaroundcenter($s, $i, $i);          // 情况 1: aba            $中兴v5sthis->expandaroundcenter($s, $i, $i + 1);      // 情况 2: bb        }        // 使用 substr 函数,截取相应的字符串        return substr($s, $this->start, $this->length);    }    /**     * @param string  $str     * @param integer $lef手机怎么玩qq农场t     * @param integer $right     */    protected function expandaroundcenter($str, $论文格式字体left, $right) {        // 这里判断左右两边对应字符是否相等,如果相等,left-1,right+1,继续比较        while ($left >= 0 && $right < $this->len && $str[$left] === $str[$right]) {            $left--;            $right++;        }        // 当上面循环结束,也就是找到了一个回文子串        // temp 是子串的长度        $temp = $right - $left - 1;        // 与 length 比较,看当前找到的子串是否是较长的那个,        // 如果是,就给 start 和 length 赋值        if ($this->length < $temp) {            $this->start  = $left + 1;            $this->length = $temp;        }    }}

本文发布于:2023-04-08 13:26:32,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/zuowen/f38abfe568f0c897f35e384ba3e8a63a.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:Leetcode 5. 最长回文子串.doc

本文 PDF 下载地址:Leetcode 5. 最长回文子串.pdf

标签:字符串   回文   长度   长度为
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图