LeetCode680- 验证回文字符串 Ⅱ-Easy
标签:贪心算法
题目:验证回文字符串 Ⅱ
题号:680
题干:给定一个非空字符串 s,最多删除一个字符。判断是否能成为回文字符串。
复制代码
思路:
遍历字符串中的每一个字符时,获取第一个字符和最后一个字符,下标分别为:$i 和 $j
如果这两个位置的字符相等,则 $i=$i+1,$j=$j-1,再次比较字符是否相等,直到循环终止条件 $i>$j
如果这两个位置的字符不相等,则依次去掉低位的字符和高位的字符。去掉低位字符,则此时起始位为 $k=$i+1,高位为 $t=$j
去掉高位字符,则此时起始位为 $k=$i,高位为 $t=$j-1
如果去掉低位和高位后,有一个能够成为回文字符串,则整个字符串为回文字符串
时间复杂度:O(n)
代码实现(语言:PHP)
复制代码
版权声明: 本文为 InfoQ 作者【书旅】的原创文章。
原文链接:【http://xie.infoq.cn/article/2a7ea91a8a048985c3557ac7b】。文章转载请联系作者。
评论