字符串-回文算法
一、定义
二、题目
- 回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
输入: 121
输出: true
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
思路：双指针class Solution:
def isPalindrome(self, x: int) -> bool:
lst=list(str(x))
i,j=0,len(lst)-1
while i<j:
if lst[i]!=lst[j]:
return False
i+=1
j-=1
return True- 验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
输入: "A man, a plan, a canal: Panama"
输出: true
输入: "race a car"
输出: false
补充基础知识
.isalnum() 检查str是否由字母和数字构成，为False时，表示里面有空格或标点符号
字符串大小写：
s.lower() 大写变小写
s.upper() 小写变大写
s.capitalize() 第一个字母变大写，其余小写
s.title（） 每个单词第一个字母变大写，其余小写
class Solution:
def isPalindrome(self, s: str) -> bool:
i=0
j=len(s)-1
s=s.lower()
while i<j:
if s[i].isalnum() and s[j].isalnum():
if s[i]==s[j]:
i+=1
j-=1
else:
return False
else:
if not s[i].isalnum(): i+=1
if not s[j].isalnum(): j-=1
return True- 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
输入: "aba"
输出: True
输入: "abca"
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
class Solution:
def validPalindrome(self, s: str) -> bool:
if s==s[::-1]: return True
i=0
j=len(s)-1
while i<j:
if s[i]!=s[j]:
a=s[:i]+s[i+1:]
if a==a[::-1]: return True
b=s[:j]+s[j+1:]
if b==b[::-1]: return True
return False
else:
i+=1
j-=1
return False- 最长回文串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意: 假设字符串的长度不会超过 1010。
输入:
"abccccdd"
输出:
7
解释:
我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
思路： 计算每个元素的个数num,若num为偶数，可直接放两边，为奇数，则num-1变偶数，最后可以留一个奇数放中间
class Solution:
def longestPalindrome(self, s: str) -> int:
b=list(set(s))
flag,oddn=0,0
for i in b:
c=s.count(i)
if c%2==1:
flag=1
oddn+=1
l=len(s)-oddn+flag
return l发布于 2020-10-21 23:11