验证回文字符串(二)

# -*- coding: utf-8 -*-

# coding:utf-8
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param str string字符串
# @return bool布尔型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/130e1a9eb88942239b66e53ec6e53f51?tpId=196&tqId=40502&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    算法：
        定义check(left, right)，用于判断字符串str中以str[i]开始，str[j]的连续字符串是否为回文串
        本题允许删除一个字符，这里我们使用deleted表示是否已经删除过。
        当str[i] != str[j]时：
            若delete = True，返回False
            否则：判断check(i, j-1)&nbs***bsp;check(i+1, j)
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O()
    """

    def palindrome(self, str):
        # write code here
        def check(left, right):
            i, j = left, right

            while i < j:
                if str[i] == str[j]:
                    i += 1
                    j -= 1
                elif self.deleted:
                    return False
                else:
                    self.deleted = True
                    return check(i + 1, j)&nbs***bsp;check(i, j - 1)

            return True

        left, right, self.deleted = 0, len(str) - 1, False

        return check(left, right)


if __name__ == "__main__":
    sol = Solution()

    # s = "nowwon"

    # s = "nowewon"

    s = "noweawon"

    # s = "noowwwn"

    res = sol.palindrome(s)

    print res