决定一个字符串是否为回文串

Question

这是一个关于Python的问题。答案应该具有O（n）时间复杂度且不使用额外的内存。我会得到一个字符串作为输入，需要将其分类为回文或非回文（回文是指一种可以从左到右和从右到左读取的单词或短语，例如“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)的复杂度。

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

- vnikonov_63

---

为什么不允许使用额外的内存如此重要？您认为从不可变字符串中删除一个字符不会创建新字符串吗？ - Mushif Ali Nawaz

@MushifAliNawaz，我知道从不可变字符串中删除一个字符会创建一个新的字符串 - 这正是我想要使用列表的原因。 - vnikonov_63

你将获得一个字符串作为输入，因此您使用的任何列表也是额外的内存。如果问题以这种方式向您提出，并且限制是为了教学目的，那么我可以保证您的教师希望您不要预处理数据，而是提出一种算法，在处理时简单地忽略非字母字符。是的，这不是解决问题的现实方法。编程课程就是这样的。 - Karl Knechtel

@vnikonov_63 你所接受的答案也会创建一个新列表，因此需要额外的内存！ :) - Mushif Ali Nawaz

请注意，range(97, 122) 不包括字母 z。 - user3386109

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

- Mushif Ali Nawaz

---

但是这会使用额外的内存，当我们声明右和左时。 - vnikonov_63

@vnikonov_63，“没有额外的内存”通常意味着在内存方面是O（1），因此单个循环变量不计入其中。 - lenik

@vnikonov_63 每个程序都使用 O(1) 的额外内存。没有办法避免这种情况。你接受的答案使用了 O(n) 的额外内存，因为列表推导式创建了一个列表。 - user3386109

在CPython中，@Niloct，它是O(1)，这是Python最常见的实现。您可以在此处阅读更多信息：len()函数的成本 - Mushif Ali Nawaz

空间复杂度实际上指的是算法根据输入如何反应存储以及额外存储空间的使用情况。例如，回文字符串的长度可以是2或50。但是，对于此算法而言，双指针变量将始终为2，无论如何。这意味着它们是常数，因此空间复杂度将为O(1)。 - ihaider

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

- SimonR

---

声明变量s的时候，我们并没有使用额外的内存，只是在对其进行修订。 - vnikonov_63

Answer 3

这里是一行使用 赋值表达式 语法（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进行比较）。

另外，您可以使用生成器表达式来进行相同的比较，而无需分配额外的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))

请注意，在Python 2中，zip仍然会分配内存，您需要使用itertools.izip。

- tzaman

---

滥用字符串推导和晦涩的语言特性从来不是好事。 - lenik

滥用是一个相当严重的词语。而赋值表达式是一项新功能，唯一摆脱模糊不清的方法就是让人们使用它！ - tzaman

Answer 4

这会有帮助吗：

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.')

- Ann Zen

---

在这里，当声明word2 =''时，您使用了额外的内存。 - vnikonov_63

考虑到运行时间和空间复杂度，这是一个糟糕的实现。首先，您正在连接字符串，这需要O（XN ^ 2）的时间复杂度。此外，您还在对列表进行排序，这需要O（N log N）的时间复杂度。 - ihaider

这段代码存在一个错误，即 "aaa" 是回文但 "a?aa" 不是。这是由于 if l.isalnum: 缺少括号导致的——也就是说，应该是 if l.isalnum():，因为你正在测试方法的存在性而不是调用它的结果。 - cdlane