顛倒Python中的字符串和迴文時間複雜度

下面的代碼是否適合檢查字符串是否是迴文件？它的時間複雜度是多少？我想是的，O(1)對不對？因爲我們只是訪問具有不同索引的相同字符串，所以訪問索引O(1)是一個操作。如果我錯了，請糾正我。如果可能，請提供更好的解決方案。顛倒Python中的字符串和迴文時間複雜度

s1 = 'abccba' 
s2 = s1[::-1] 
if s1==s2: 
    print 'Palindrome' 
else: 
    print 'Not Palindrome'

來源

2015-04-04 Harsh Vardhan Ladha

最壞情況複雜度爲O（N）。除此之外，比較兩個字符串的最差情況是O（n）。所以，這個解決方案的複雜性是O（n）。 – thefourtheye 2015-04-04 12:32:47

同意！但它是一個很好的方法來使用？或者有更好的方法可以在那裏？ – 2015-04-04 12:41:08

def check_palin(word): 
    for i in xrange(len(word)/2): 
     if word[i] != word[-(i+1)]: 
      return False 
    return True

我想這是一個比較有效的解決方案，因爲它遍歷字符串的一半，只要條件被破壞返回False。但複雜性仍然是O(n)

來源

2015-04-04 12:41:56 ZdaR

' - （i + 1）'？ – thefourtheye 2015-04-04 12:45:23

@thefourtheye：都是一樣的，'-1 *（i + 1）'和' - （i + 1）' – 2015-04-04 13:18:19

是啊@HarshVardhanLadha但是 - （i + 1）'更清潔一點 – ZdaR 2015-04-04 13:20:05

-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"))

來源

2015-04-04 13:32:04 ajkumar25

我不確定您知道這種情況下的複雜性意味着什麼。複雜度衡量了查看不同輸入大小時需要完成的操作量。如果檢查迴文是O（1），這意味着檢查一個大小爲2的字符串將與10000的大小相同。在這種情況下，這是不正確的，因爲您需要進行n/2次檢查。這意味着它在） – 2015-04-04 13:42:25

我已經寫了代碼，它的工作原理正是我wanted.please檢查切片

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

來源

2018-03-01 11:16:33

顛倒Python中的字符串和迴文時間複雜度

回答

相關問題