Lc 125 验证回文字符串
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。
class Solution:
def judgeNumOrStr(self,a):
if ord('0')<=ord(a)<=ord('9') or ord('a')<=ord(a)<=ord('z'):
return True
else:
return False
def isPalindrome(self, s: str) -> bool:
s = s.lower()
i,j = 0,len(s)-1
while i<j:
if not self.judgeNumOrStr(s[i]):
i+=1
continue
if not self.judgeNumOrStr(s[j]):
j-=1
continue
if s[i] != s[j]:
return False
i+=1
j-=1
return True
Lc 680 验证回文字符串Ⅱ
给定一个非空字符串 s
,最多删除一个字符。判断是否能成为回文字符串。
先写一个单独验证回文字符串的函数A,然后判断的时候如果不相等则调用A判断 [i+1,j] 或者 [i,j-1]是否为回文
class Solution:
def judgestr(self,s,i,j):
while i<j:
if s[i] != s[j]:
return False
i+=1
j-=1
return True
def validPalindrome(self, s: str) -> bool:
i, j = 0,len(s)-1
count = 0
while i<j:
if s[i] != s[j]:
if self.judgestr(s,i+1,j) or self.judgestr(s,i,j-1):
return True
else:
return False
i+=1
j-=1
return True
Lc 234 回文链表
请判断一个链表是否为回文链表。
用 O(n) 时间复杂度和 O(1) 空间复杂度解决
用快慢指针找到中间节点,反转后半部分,然后进行对比
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseList(self,head):
pre = None
p = head
while p:
nextNode = p.next
p.next = pre
pre = p
p = nextNode
return pre
def isPalindrome(self, head: ListNode) -> bool:
if not head or not head.next:
return True
slow,fast = head,head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
left = head
right = self.reverseList(mid)
while left and right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
Lc 5 最长回文子串
给定一个字符串 s
,找到 s
中最长的回文子串。你可以假设 s
的最大长度为 1000。
动态规划:
判断s[i,j]时,需要知道s[i+1,j-1]的状态,因此遍历时i从大到小(n-1->0),j从小到大(i->n-1)
class Solution:
def longestPalindrome(self, s: str) -> str:
if not s or len(s) == 0:
return ""
n,start,maxlen = len(s),0,0
d = [[False]*n for _ in range(n)]
for i in range(n-1,-1,-1):
for j in range(i,n):
if i==j:
d[i][j] = True
elif i+1==j:
d[i][j] = (s[j] == s[i])
else:
d[i][j] = ((s[i]==s[j]) and d[i+1][j-1])
if d[i][j] and j-i+1>maxlen:
maxlen = (j-i+1)
start = i
return s[start:start+maxlen]