FIFA-2022 Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
375 views
in Coding Questions by Goeduhub's Expert (2.3k points)

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

 

Constraints:

  • s consists only of printable ASCII characters.

1 Answer

0 like 0 dislike
by Goeduhub's Expert (2.3k points)
 
Best answer

One way to solve this problem is to create new string with only alphanumeric symbols and then check if it is palindrome. However we need O(n) space for this. There is more subtle approach, using Two Pointers technique.

  • Start with beg = 0 and end = len(s) - 1, the first and the last symbols of string s.
  • Now, we are going to move iterator beg only to the right and iterator end only to the left. Let us move them, until we reach alphanumeric symbols, using isalnum() function.
  • Compare these two symbols. We are happy, if they are equal, or it is the same letter in different capitalization, for example q and Q. How to check this case? Make both symbols capitalized, using .upper() and compare them.
  • In opposite case, immidietly return False.
  • If we reached the end of or program and we did not return False, then we need to return True.

Complexity: Time complexity is O(n), because we move beg only to the right and end only to the left, until they meet. Space complexity is O(1), we just use a couple of additional variables.

class Solution:

    def isPalindrome(self, s):

        beg, end = 0, len(s) - 1

        while beg <= end:

            while not s[beg].isalnum() and beg < end: beg += 1

            while not s[end].isalnum() and beg < end: end -= 1

            if s[beg] == s[end] or s[beg].upper() == s[end].upper():

                beg, end = beg + 1, end - 1

            else:

                return False

        return True

eg : ans = Solution()

ans.isPalindrome("race a car")

Output -

False

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

Related questions

0 like 0 dislike
1 answer 224 views
asked Sep 1, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 286 views
asked Sep 13, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 628 views
asked Sep 15, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 644 views
asked Sep 15, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
0 like 0 dislike
1 answer 3.1k views
asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory

...