CODEWITHSUNDEEP
pythonalgorithmtime-complexityspace-complexity
vnikonov_63
vnikonov_63

Reputation: 191

Deciding whether a string is a palindrome

This is a python question. Answer should be with O(n) time complexity and use no additional memory. As input i get a string which should be classified as palindrome or not (palindrome is as word or a phrase that can be read the same from left to right and from right to left, f.e "level"). In the input there can be punctuation marks and gaps between words. For example "I. did,,, did I????" The main goal is to decide whether the input is a palindrome.

When I tried to solve this question i faced several challenges. When I try to delete non letter digits

for element in string:
    if ord(element) not in range(97, 122):
        string.remove(element)
    if ord(element) == 32:
        string.remove(element)

I use O(n^2) complexity, because for every element in the string i use remove function, which itself has O(n) complexity, where n is the length of the list. I need help optimizing the part with eliminating non letter characters with O(n) complexity

Also, when we get rid of spaces as punctuation marks I know how to check whether a word is a palindrome, but my method uses additional memory.

Upvotes: 3

Views: 560

Answers (4)

SimonR
SimonR

Reputation: 1824

I'm assuming you mean you want to test if a string is a palindrome when we remove all punctuation digits from the string. In that case, the following code should suffice:

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

Upvotes: 4

Red
Red

Reputation: 27577

Will this help:

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

Upvotes: 0

tzaman
tzaman

Reputation: 47820

Here's a one-liner using assignment expression syntax (Python 3.8+):

>>> s =  "I. did,,, did I????"
>>> (n := [c.lower() for c in s if c.isalpha()]) == n[::-1]
True

I mostly showed the above as a demonstration; for readability's sake I'd recommend something more like SimonR's solution (although still using isalpha over comparing to ascii_letters).

Alternatively, you can use generator expressions to do the same comparison without allocating O(n) extra memory:

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

Note that zip still allocates in Python 2, you'll need to use itertools.izip there.

Upvotes: 1

Mushif Ali Nawaz
Mushif Ali Nawaz

Reputation: 3866

Here is your O(n) solution without creating a new string: 

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

Output:

True

Upvotes: 5

Related Questions