Jianbo Dai's

mq004.验证回文串

 
  • Nov 04, 2020

题目链接这个题可以用双指针法，如下所示，这个算法的时间复杂度是O（N），空间复杂度是O（N）。我们完全可以在原字符串上进行判断从而优化空间复杂度，使其减小为O（1）。

class Solution:
    def isPalindrome1(self, s: str) -> bool:
        sp = "".join(ch.lower() for ch in s if ch.isalnum())
        i, j = 0, len(sp)-1
        while i < j:
            if sp[i].lower() != sp[j].lower():
                return False
            i += 1
            j -= 1
        return True

    def isPalindrome2(self, s: str) -> bool:
        i, j = 0, len(s)-1
        while i < j:
            while i < j and not s[i].isalnum():
                i += 1
            while i < j and not s[j].isalnum():
                j -= 1
            if i < j and s[i].lower() != s[j].lower():
                return False
            i += 1
            j -= 1
        return True
Search