Description
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
Solutions
1. String
# Time: O(n)
# Space: O(n)
class Solution:
def isPalindrome(self, s: str) -> bool:
strs = ''
alphet = list('abcdefghijklmnopqrstuvwxyz0123456789')
s = s.lower()
for ch in s:
if ch in alphet:
strs += ch
n = len(strs)
l, r = n // 2, n // 2
if n % 2 == 0:
l -= 1
while l >= 0 and r < n:
if strs[l] != strs[r]:
return False
l -= 1
r += 1
return True
# 476/476 cases passed (80 ms)
# Your runtime beats 9.19 % of python3 submissions
# Your memory usage beats 84.52 % of python3 submissions (13.3 MB)
不要非要从中间开始遍历嘛,这样要使用到除法以及取模操作,两个指针从两边出发往中间行进也是可以的啊。
# Time: O(n)
# Space: O(n)
class Solution:
def isPalindrome(self, s: str) -> bool:
l, r = 0, len(s) - 1
while l < r:
while l < r and not s[l].isalnum():
l += 1
while l < r and not s[r].isalnum():
r -= 1
if s[l].lower() != s[r].lower():
return False
l += 1
r -= 1
return True
# 476/476 cases passed (48 ms)
# Your runtime beats 61.55 % of python3 submissions
# Your memory usage beats 76.19 % of python3 submissions (13.3 MB)