Reversing a string and palindrom time complexity in Python

Question

Is the code below code good for checking whether a string is palindrome or not? What is its time complexity? I guess it's, O(1) am I right? Because we are just accessing the same string with different indexes and so accessing index O(1) is an operation. Please correct me if I'm wrong. Please provide a better solution, if possible.

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

Worst case complexity of slicing is O(n). Apart from that, worst case complexity of comparing two strings is O(n). So, the complexity of this solution is O(n). — thefourtheye, Apr 04 '15 at 12:32
Agree! but is it a good method to use ? or any better method can be there? — Harsh Vardhan Ladha, Apr 04 '15 at 12:41

ZdaR · Accepted Answer · 2021-06-21T04:59:13.220

8

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

I guess this is a bit more efficient solution as it iterates over half of the string and returns False whenever the condition is violated. But still the complexity would be O(n)

edited Jun 21 '21 at 04:59

answered Apr 04 '15 at 12:41

ZdaR

22,343
7
66
87

to make sure the for loop range is in integer, we need to do an integer division by using `//` `for i in range(len(word)//2):` – Sankar Jun 20 '21 at 07:39
Sure @Sankar, For Python2.x we can use `/`, for Python 3.x we should use `//`. But for the sake of consistency, I will edit the answer to use `//`. Thanks for pointing out. – ZdaR Jun 21 '21 at 04:59

Reversing a string and palindrom time complexity in Python

1 Answers1