Check if the characters in a string form a Palindrome in O(1) extra space

def firstPos(str, start, end):

firstChar = -1

for i in range(start, end + 1):

if (str[i] >= 'a' and str[i] <= 'z') :

firstChar = i

break

return firstChar

def lastPos(str, start, end):

lastChar = -1

for i in range(start, end - 1, -1) :

if (str[i] >= 'a' and str[i] <= 'z') :

lastChar = i

break

return lastChar

def isPalindrome(str):

firstChar = 0

lastChar = len(str) - 1

ch = True

for i in range(len(str)) :

firstChar = firstPos(str, firstChar, lastChar);

lastChar = lastPos(str, lastChar, firstChar);

if (lastChar < 0 or firstChar < 0):

break

if (str[firstChar] == str[lastChar]):

firstChar += 1

lastChar -= 1

continue

ch = False

break

return (ch)

if __name__ == "__main__":


str = "m a 343 la y a l am"

if (isPalindrome(str)):

print("YES")

else:

print("NO")

 

No comments: