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.
1 2 3 4 5 6 7 8 9 10 11 12 13 | 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 |
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 TrueUsing Filter and provide a lambda function:
1 2 3 4 | class Solution: def solve(self, s): s0 = list(filter(lambda x: x.islower(), s)) return s0 == s0[::-1] |
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.
1 2 3 4 5 | 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)) |
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.
1 2 3 4 5 | 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 |
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 == s1Another simple implementation filtering out non-lowercase letters:
1 2 3 4 | class Solution: def solve(self, s): a = [c for c in s if c.islower()] return a == a[::-1] |
class Solution:
def solve(self, s):
a = [c for c in s if c.islower()]
return a == a[::-1]or:
1 2 3 4 | class Solution: def solve(self, s): a = list(c for c in s if c.islower()) return a == a[::-1] |
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).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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 |
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 TrueAlso, use the lambda inline:
1 2 3 | class Solution: def solve(self, s): return (lambda s: s == s[::-1])([c for c in s if c.islower()]) |
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) —
loading...
Last Post: Using sys_getloadavg and num_cpus in PHP to Throttle API
Next Post: An Example Email to Negotiate Your Package (Salary) - Counter Offer Template
