LeetCode 125. Valid Palindrome.jpg
LeetCode 125. Valid Palindrome
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
描述
給定一個字符串茬祷，驗(yàn)證它是否是回文串，只考慮字母和數(shù)字字符祭犯，可以忽略字母的大小寫。
說明：本題中粥惧，我們將空字符串定義為有效的回文串最盅。
示例 1:
輸入: "A man, a plan, a canal: Panama"
輸出: true
示例 2:
輸入: "race a car"
輸出: false
思路
- 回文字符串是指字符串呈中心對成，即第一個字符與最后一個字符相等咏删，第二個字符與倒數(shù)第二個字符相等.
- 我們用兩個指針问词，一共從前往后遍歷，一個從后往前遍歷即可，需要注意的是我們只比較字母和數(shù)字锋叨，其他情況直接跳過.
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-03 11:16:37
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-03 11:34:21
class Solution:
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
if not s:
return True
left, right = 0, len(s)-1
while left < right:
# 如果當(dāng)前字符是數(shù)字或者字母
if (s[left].isalpha() or s[left].isdigit()) and (s[right].isalpha() or s[right].isdigit()):
# 如果相等則left向后走一步宛篇，right向前走一步
if s[left].lower() == s[right].lower():
left += 1
right -= 1
else:
# 否則返回False
return False
# 如果左邊不是數(shù)字或者字符，則認(rèn)為是滿足回文符串的條件
elif not (s[left].isalpha() or s[left].isdigit()):
left += 1
# 如果右邊不是數(shù)字或者字符偷卧，則認(rèn)為是滿足回文字符串的條件
elif not (s[right].isalpha() or s[right].isdigit()):
right -= 1
return True
if __name__ == "__main__":
so = Solution()
res = so.isPalindrome("0P")
源代碼文件在這里.
?本文首發(fā)于何睿的博客段标，歡迎轉(zhuǎn)載炉奴，轉(zhuǎn)載需保留文章來源，作者信息和本聲明.
