美文网首页
891. Valid Palindrome II

891. Valid Palindrome II

作者: 小时候浪死了 | 来源:发表于2018-09-14 17:17 被阅读0次

    Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
    (给定非空字符串s,您最多可以删除一个字符。 判断是否可以成为回文)
    样例

    Given s = "aba" return true
    Given s = "abca" return true // delete c

    解:考虑到有两种情况(以下字符串的空格间隔是为了方便区分看)
    1)string s="a b d b c a" 这里应该删掉s[4];

    1. string s="a c b d b a" 这里应该删掉s[1];
    bool validPalindrome(string &s) {
            // Write your code here
            int h=s.length()-1;
            int l=0;
            bool work=false;
            if(h<=1) 
                return true;
            while(l<h)
            {
                if(s[l]==s[h])
                {
                    l++;
                    h--;
                }
                else
                {
                    if(work==false)//因为最多只能删除一个,所以这里用个bool来判别执行一次
                    {
                        if(s[l]==s[h-1]) //上面所说的情况一
                        {
                            h-=2;
                            l++;
                        }
                        else if(s[l+1]==s[h])//情况二
                        {
                            l+=2;
                            h--;
                        }
                        work=true;//删除一次后,设置为true,因为至多删除一个
                    }
                    else
                        return false;
                }
            }
            return true;
        }
    

    相关文章

      网友评论

          本文标题:891. Valid Palindrome II

          本文链接:https://www.haomeiwen.com/subject/vmaogftx.html