以下题目均来自LeetCode。
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
输入: "cbbd"
输出: "bb"
Answer:
class Solution:
def longestPalindrome(self, s: str) -> str:
if len(s) == 0:
return s
dp = [[False]*len(s) for _ in range(len(s))]
dp[0][0]=True
ans = ""
for l in range(len(s)):
for i in range(len(s)):
end = l+i
if end>=len(s):
break
if end == i:
dp[i][end] = True
elif l == 1:
dp[i][end] = (s[i]==s[end])
else:
dp[i][end] = (dp[i + 1][end - 1] and s[i] == s[end])
if dp[i][end] and len(s[i:end+1])>len(ans):
ans = s[i:end+1]
return ans
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回 s 所有可能的分割方案。
输入: "aab"
输出:
[
["aa","b"],
["a","a","b"]
]
Answer: 思路1:使用回溯法,相当于$dp[i,k] = \sum dp[i,j]+str[j:k]$,其中str[j:k]是回文串
class Solution:
def partition(self, s: str) -> List[List[str]]:
res = []
def forward(string,subresult):
if not string:
res.append(subresult)
for i in range(1,len(string)+1):
if string[:i] == string[:i][::-1]:
forward(string[i:],subresult+[string[:i]])
forward(s,[])
return res
思路2:联系上一题,先确定dp[i,j]是否是回文串,再DFS遍历所有可能的路径,也就是dp[0,i]+dp[i,j]+dp[j,k]+dp[k,n],这解法转载自powcai
class Solution:
def partition(self, s: str) -> List[List[str]]:
result= []
n = len(s)
dp = [[False]*n for _ in range(n)]
dp[0][0] = True
for i in range(n):
for j in range(i+1):
if s[i] == s[j] and (i-j<=2 or dp[j+1][i-1]==True):
dp[j][i] = True
def recall(idx,subresult):
if idx==n:
result.append(subresult)
for i in range(idx,n):
if dp[idx][i]:
recall(i+1,subresult+[s[idx:i+1]])
recall(0,[])
return result
给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。 具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。
输入: "aaa"
输出: 6
说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
Answer: 思路1:如题目2,采用动态规划
class Solution:
def countSubstrings(self, s: str) -> int:
count = 0
n = len(s)
dp = [[False]*n for _ in range(n)]
for i in range(n):
for j in range(i+1):
if s[i] == s[j] and (i-j<=2 or dp[j+1][i-1]):
dp[j][i]=True
count+=1
return count
给定一个字符串,验证它是否是回文串,只考虑字母和数字字符,可以忽略字母的大小写。 说明:本题中,我们将空字符串定义为有效的回文串。
输入: "A man, a plan, a canal: Panama"
输出: true
Answer: 思路:清除无效字符
class Solution:
def isPalindrome(self, s: str) -> bool:
if len(s) == 0:
return True
s = s.lower()
def Valid(char):
if (char>='0' and char<='9') or (char>='a' and char<='z') or(char>='A' and char<='Z'):
return True
return False
string = []
for char in s:
if Valid(char):
string.append(char)
string = ''.join(string)
if string == string[::-1]:
return True
return False
给你一个回文字符串 palindrome ,请你将其中 一个 字符用任意小写英文字母替换,使得结果字符串的字典序最小,且 不是 回文串。 请你返回结果字符串。如果无法做到,则返回一个空串。
输入:palindrome = "abccba"
输出:"aaccba"
输入:palindrome = "a"
输出:""
Answer: 思路:字典序最小,也就是要填充尽可能小的字符,比如ab>aa,所以要尽可往前填a,当遇到所有都是a时,要在最后一位填b。 由于是回文串,所以前一半和后一半是相同的,我们只要遍历前一半就好,如果前一半都是a,那么后一半也全是a,所以要修改回文串且字典序最小,则在最后一位将a变为b
class Solution:
def breakPalindrome(self, palindrome: str) -> str:
n = len(palindrome)
if n<2:
return ""
for i in range(int(n/2)):
if palindrome[i]!='a':
return palindrome[:i]+'a'+palindrome[i+1:]
return palindrome[:n-1]+'b'
给定一个字符串 s,将 s 分割成一些子串,使每个子串都是回文串。 返回符合要求的最少分割次数。
输入: "aab"
输出: 1
解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
Answer: 思路1:采用回溯+剪枝,但还是会超时,时间为$O(N^2)$。
class Solution:
def minCut(self, s: str) -> int:
if len(s)<2:
return 0
min_cut = [len(s)]
def recall(sub,current_cut):
if not sub:
min_cut[0] = min(min_cut[0],current_cut-1)
if min_cut[0]<current_cut:
return
for i in range(1,len(sub)+1):
if sub[:i] == sub[:i][::-1]:
recall(sub[i:],current_cut+1)
recall(s,0)
return min_cut[0]
思路2:采用动态规划,dp[i,j]表示s[i:j+1]是回文串,然后再构建最短路
class Solution:
def minCut(self, s: str) -> int:
n = len(s)
dp = [[False]*n for _ in range(n)]
for i in range(n):
for j in range(i+1):
if s[i] == s[j] and (i-j<=2 or dp[j+1][i-1]):
dp[j][i]=True
res = [n]*n
for i in range(n):
if dp[0][i]:
res[i]=0
continue
for j in range(0,i):
if dp[j+1][i]:
res[i] = min(res[i],res[j]+1)
return res[n-1]
给你一个由小写字母组成的字符串 s,和一个整数 k。
请你按下面的要求分割字符串: 首先,你可以将 s 中的部分字符修改为其他的小写英文字母。 接着,你需要把 s 分割成 k 个非空且不相交的子串,并且每个子串都是回文串。 请返回以这种方式分割字符串所需修改的最少字符数。
输入:s = "abc", k = 2
输出:1
解释:你可以把字符串分割成 "ab" 和 "c",并修改 "ab" 中的 1 个字符,将它变成回文串。
输入:s = "aabbc", k = 3
输出:0
解释:你可以把字符串分割成 "aa"、"bb" 和 "c",它们都是回文串。
Answer: 思路1:采用动态规划,dp[i][j]表示s[:i]分为j段要修改的次数 $dp[i][j] = min(dp[k][j-1]+const(s[k+1:i])$ const表示将参数变为回文串需要修改的次数 算法时间复杂度有待提高
class Solution:
def palindromePartition(self, s: str, k: int) -> int:
n = len(s)
def const(subs):
p1 = 0
p2 = len(subs)-1
count = 0
while p1<p2:
if not subs[p1] == subs[p2]:
count+=1
p1+=1
p2-=1
return count
dp = [[10**9]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,min(k,i)+1):
if j == 1:
dp[i][j] = const(s[:i])
else:
#k>j-1才有意义
for t in range(j-1,i):
dp[i][j] = min(dp[i][j],dp[t][j-1]+const(s[t:i]))
return dp[n][k]
思路2:预处理const函数,可以看到const函数调用了O(N^3)次,而const本质上可以在O(N^2)内遍历完。
给定一个字符串 s,你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。
输入: "aacecaaa"
输出: "aaacecaaa"
输入: "abcd"
输出: "dcbabcd"
Answer: 思路1:先判断s[0:t]是回文串,或t==1,则开头不包含回文串,或t==n,则表示整体是一个回文串。
class Solution:
def shortestPalindrome(self, s: str) -> str:
n = len(s)
if n<2:
return s
idx = 1
for i in range(2,n+1):
if s[0:i] == s[0:i][::-1]:
idx = i
if idx == n:
return s
else:
return s[idx:][::-1]+s