Login light

超出时间限制

class Solution {

    /**
     * @param String $s
     * @return Boolean
     */
    function validPalindrome($s) {
        $sRev = strrev($s);
        if ($s === $sRev) {
            return true;
        }
        $strlen = strlen($s);
        $index = 0;
        while ($index < $strlen) {
            if (0 === $index) {
                $str = substr($s, 1);
            } else if ($strlen - 1 === $index) {
                $str = substr($s, 0, $strlen - 1);
            } else {
                $str = substr($s, 0, $index) . substr($s, $index + 1, $strlen);
            }
            if ($str === strrev($str)) {
                return true;
            }
            $index++;
        }
        return false;
    }
}

递归

class Solution {

    /**
     * @param String $s
     * @return Boolean
     */
    function validPalindrome($s) {
        return $this->loop($s, 0, strlen($s) - 1, 1);
    }
    /**
     * @param $str 输入字符串
     * @param $head
     * @param $foot
     * @param $num 可删除的次数
     * @return bool
     */
    function loop(string &$str, int $head, int $foot, int $num) {
        //判断$head $foot是否一致
        if ($str[$head] === $str[$foot]) {
            //判断返回点
            if ($foot - $head <= 2) {
                return true;
            } else {
                return $this->loop($str, $head + 1, $foot - 1, $num);
            }
        } else {
            if (1 === $num) {
                //左边或右边跳过一个字母
                return $this->loop($str, $head + 1, $foot, 0) or $this->loop($str, $head, $foot - 1, 0);
            } else {
                return false;
            }
        }
    }
}

4指针(jessie)
https://leetcode-cn.com/problems/valid-palindrome-ii/solution/si-ge-zhi-zhen-jie-da-by-jessie-ii/

class Solution {
    public boolean validPalindrome(String s) {
        int i1 = 0;
        int j1 = s.length() - 1;
        int i2 = 0;
        int j2 = s.length() - 1;
        boolean flag = true;
        
        while (i1<j1 || i2 <j2)
        {
            if (s.charAt(i1) == (s.charAt(j1)) || s.charAt(i2) == (s.charAt(j2)))
            {
                i1++;
                j1--;
                i2++;
                j2--;
            }
            else
            {      
                if (flag)   
                {
                    if (s.charAt(i1)==(s.charAt(j1-1)) || s.charAt(i2+1)==(s.charAt(j2)))
                    { 
                        i1++;
                        j1--;
                        j1--;
                        i2++;
                        i2++;
                        j2--;
                        flag = false;
                    }
                    else
                    {
                        return false;
                    }
                }  
                else
                {
                    return false;
                }                                                     
                                   
            }
        }
        return true;
    }
}