确定字符串是否是回文

Question

这是一个python问题。答案应该是O（n）时间复杂度，并且不使用额外的内存。作为输入，我得到一个字符串，该字符串应分类为回文或不分类（回文是可以从左到右和从右到左读作相同的单词或短语，例如“ level”）。在输入中可能存在标点符号和单词之间的间隙。例如“我做了，我做了吗？？？？”主要目标是确定输入的内容是否是回文。

[当我试图解决这个问题时，我面临着几个挑战。当我尝试删除非字母数字时

for element in string:
    if ord(element) not in range(97, 122):
        string.remove(element)
    if ord(element) == 32:
        string.remove(element)

我使用O（n ^ 2）的复杂度，因为对于字符串中的每个元素，我都使用remove函数，该函数本身具有O（n）的复杂度，其中n是列表的长度。我需要帮助来优化零件，以消除复杂度为O（n）的非字母字符

而且，当我们去除空格作为标点符号时，我知道如何检查单词是否是回文，但是我的方法使用了额外的内存。

Answer 1

这是您的O（n）解决方案，无需创建新字符串：

def is_palindrome(string):
    left = 0
    right = len(string) - 1

    while left < right:
        if not string[left].isalpha():
            left += 1
            continue
        if not string[right].isalpha():
            right -= 1
            continue

        if string[left] != string[right]:
            return False

        left += 1
        right -= 1

    return True


print(is_palindrome("I. did,,, did I????"))

输出：

True

Answer 2

我假设您的意思是，当我们从字符串中删除所有标点符号/数字时，您想测试字符串是否是回文。在这种情况下，下面的代码就足够了：

from string import ascii_letters

def is_palindrome(s):
    s = ''.join(c for c in s if c in ascii_letters)
    return s == s[::-1]

# some test cases:
print(is_palindrome('hello'))  # False
print(is_palindrome('ra_ceca232r'))  # True

Answer 3

这里是使用assignment expression语法（Python 3.8+）的单行代码：

>>> s =  "I. did,,, did I????"
>>> (n := [c.lower() for c in s if c.isalpha()]) == n[::-1]
True

---

我主要是为了演示上述内容；出于可读性考虑，我建议使用类似于SimonR的解决方案（尽管与isalpha相比仍然使用ascii_letters。）>

或者，您可以使用generator expressions进行相同的比较，而无需分配O(n)额外的内存：

def is_palindrome(s):
    forward = (c.lower() for c in s if c.isalpha())
    back = (c.lower() for c in reversed(s) if c.isalpha())
    return all(a == b for a, b in zip(forward, back))
请注意，zip仍在Python 2中进行分配，您需要在其中使用itertools.izip。

Answer 4

将提供帮助：