Teaching Kids Programming – Noisy Palindrome Algorithms

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a string s containing lowercase and uppercase alphabet characters as well as digits from “0” to “9”. Return whether s is a palindrome if we only consider the lowercase alphabet characters.

Constraints
0 ≤ n ≤ 100,000 where n is the length of s
Example 1
Input
s = “a92bcbXa”
Output
True
Explanation
If we only consider the lowercase characters, then s is “abcba” which is a palindrome.

Example 2
Input
s = “abZ”
Output
False

Algorithms to Check Noisy Palindrome

We can use s.islower() to filter out the characters we want and then do a normal palindrome check. The following Python constructs a new string, and then use two pointer to check if it is a palindrome.

class Solution:
    def solve(self, s):
        x = ""
        for i in s:
            if i.islower():
                x += i
        i, j = 0, len(x) - 1
        while i <= j:
            if x[i] != x[j]:
                return False
            i += 1
            j -= 1
        return True

Using Filter and provide a lambda function:

class Solution:
    def solve(self, s):
        s0 = list(filter(lambda x: x.islower(), s))
        return s0 == s0[::-1]

Also, we can use list comprehension to create two list/tuple, and then check if both lists/tuples are the same.

class Solution:
    def solve(self, s):
        s0 = (a for a in s if a.islower())
        s1 = (a for a in reversed(s) if a.islower())
        return all(a == b for a, b in zip(s0, s1))

If both are lists, we can directly compare for equality.

class Solution:
    def solve(self, s):
        s0 = [a for a in s if a.islower()]
        s1 = [a for a in reversed(s) if a.islower()]
        return s0 == s1

Another simple implementation filtering out non-lowercase letters:

class Solution:
    def solve(self, s):
        a = [c for c in s if c.islower()]
        return a == a[::-1]

or:

class Solution:
    def solve(self, s):
        a = list(c for c in s if c.islower())
        return a == a[::-1]

We can skip to next lowercase characters using two pointers – complexity O(N). Space complexity O(1).

class Solution:
    def solve(self, s):
        n = len(s)
        i, j = 0, n - 1
        while i < j:
            while i < j and (not s[i].islower()):
                i += 1
            while i < j and (not s[j].islower()):
                j -= 1
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

Also, use the lambda inline:

class Solution:
    def solve(self, s):
        return (lambda s: s == s[::-1])([c for c in s if c.islower()])

See also: Noisy Palindrome Algorithm (Check Lowercase Palindrome Strings)

–EOF (The Ultimate Computing & Technology Blog) —