判断一个字符串是否为回文

Question

这是一个 python 问题。答案应该是 O(n) 时间复杂度并且不使用额外的内存。作为输入，我得到一个字符串，它是否应该被归类为回文（回文是可以从左到右和从右到左阅读相同的单词或短语，f.e "level"）。在输入中，单词之间可以有标点符号和空格。例如"I. did,,, did I????"主要目标是判断输入是否为回文

当我试图解决这个问题时，我遇到了几个挑战。当我尝试删除非字母数字时

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

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

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 2

这有帮助吗：

word = input('Input your word: ')
word1 = ''
for l in word:
    if l.isalnum():
        word1 += l
word2=''
for index in sorted(range(len(word1)),reverse=True):
    word2+=word1[index]
if word1 == word2:
    print('It is a palindrone.')
else:
    print('It is not a palindrone.')

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 的解决方案（尽管与 ascii_letters 相比仍然使用 isalpha）。

或者，您可以使用 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

这是不创建新字符串的 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

判断一个字符串是否为回文

Deciding whether a string is a palindrome

python

algorithm

time-complexity

space-complexity

这有帮助吗：