您的位置 首页 php

LeetCode面试题目——PHP实现最短回文串

题目

给定一个字符串 s,你可以通过在 字符串 前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1:

 输入: "aacecaaa"
输出: "aaacecaaa"
  

示例 2:

 输入: "abcd"
输出: "dcbabcd"
  

简单说明

我们先写个判断字符串是否为回文的函数,然后从右往左一点点往里面填,拼接到旧的字符串上,判断是不是回文串,如果是的话,直接返回即可

代码

 class Solution {

    /**
     * Created by 沙蒿.
     * @desc 生成回文字符串
     * @param $s
     * @return string
     */    function shortest_palindrome($s)
    {
        $temp = '';
        $len  = strlen($s);
        if ($len > 1) {
            if (!$this->is_palindrome($s)) {
                for ($i = 0; $i < $len - 1; $i++) {
                    //每一次从尾部依次取一个下标字符串到前面
                    $temp = $temp . $s[$len - 1 - $i];
                    if ($this->is_palindrome($temp . $s)) {
                        return $temp . $s;
                    }
                }
            }
        }
        return $s;
    }

    /**
     * Created by 沙蒿.
     * @desc 判断是否为回文字符串
     * @param $string
     * @return bool
     */    function is_palindrome($string)
    {
        $len    = strlen($string);
        $is_odd = ($len % 2 == 0) ? 0 : 1;
        $midd   = $len / 2;
        //从0位置开始,截取字符串前几位数字
        $f_string = substr($string, 0, $midd);
        //从上一个截取的结束位置起(奇数 + 1),截取字符串后几位数字,并反转字符串
        $b_string = strrev(substr($string, $midd + $is_odd, $midd));
        if ($f_string != $b_string) {
            return false;
        }
        return true;
    }
}
  

结果

提交结果:提交通过

通过 测试用例 :120/120

语言:php

执行用时:632 ms

消耗内存:15.3 MB

文章来源:智云一二三科技

文章标题:LeetCode面试题目——PHP实现最短回文串

文章地址:https://www.zhihuclub.com/153617.shtml

关于作者: 智云科技

热门文章

网站地图