在Python中扭转字符串和回文时间复杂度

问题描述 投票:1回答:3

下面的代码是否适合检查字符串是否是回文?它的时间复杂度是多少?我想是的,O(1)我是对的吗?因为我们只是访问具有不同索引的相同字符串,所以访问索引O(1)是一个操作。如果我错了,请纠正我。如果可能,请提供更好的解决方案。

s1 = 'abccba'
s2 = s1[::-1]
if s1==s2:
    print 'Palindrome'
else:
    print 'Not Palindrome'
python string list palindrome
3个回答
3
投票
def check_palin(word):
    for i in xrange(len(word)/2):
        if word[i] != word[-(i+1)]:
            return False
    return True

我想这是一个更有效的解决方案,因为它迭代超过一半的字符串并在违反条件时返回False。但仍然复杂的是O(n)


0
投票

我已经编写了一个代码,它完全符合我的需求。请检查

def reverse(word):
    x = ''
    for i in range(len(word)):
        x += word[len(word)-1-i]
        return x

word = input('give me a word:\n')
x = reverse(word)
if x == word:
    print('This is a Palindrome')
else:
    print('This is NOT a Palindrome')

-2
投票

Deque支持线程安全,内存高效的追加和双端队列的弹出,在任一方向上具有大致相同的O(1)性能。所以我们可以使用deque来检查回文串,它可以在O(1)中工作。

from collections import deque


def palindrome_checker(string):
    char_deque = deque()

    for ch in string:
        char_deque.appendleft(ch)

    still_equal = True

    while len(char_deque) > 1 and still_equal:
        first = char_deque.pop()
        last = char_deque.popleft()
        if first != last:
            still_equal = False

    return still_equal

print(palindrome_checker("lsdkjfskf"))
print(palindrome_checker("radar"))
© www.soinside.com 2019 - 2024. All rights reserved.