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