第五期来啦。本期主题是很常见的回文串专题，经常遇到，核心问题解题步骤固定，需要重点掌握。整理出模板，加快解题速度。
本期为期一个月，每周一三五早上八点半左右更新。
参考资料
第一周
周一： 5. 最长回文子串
先了解基本原理，解决基本问题
3 个赞
中心扩散算法
func longestPalindrome(s string) string {
start, end := 0, 0
for i := range s {
l, r := diffusion(s, i, i)
if r-l > end-start {
start, end = l, r
}
l, r = diffusion(s, i, i+1)
if r-l > end-start {
start, end = l, r
}
}
return s[start:end+1]
}
func diffusion(s string, l, r int) (int, int) {
for ;l>=0 && r<len(s) && s[l] == s[r]; l, r = l-1, r+1 {}
return l+1, r-1
}
1 个赞
// CreateTime: 2021-03-01 19:28:31
class Solution {
public:
string ans = "";
string longestPalindrome(string s) {
int len = s.size();
for (int i = 0; i < len; i++) {
tryExpand(s, i, i);
tryExpand(s, i, i+1);
}
return ans;
}
void tryExpand(string &s, int k1, int k2) {
int len = s.size();
while (k1 >= 0 && k2 < len && s[k1] == s[k2]) {
if (k2-k1+1 > ans.size()) {
ans = s.substr(k1, k2-k1+1);
}
k1--;
k2++;
}
}
};
125
go
func isPalindrome(s string) bool {
sLen := len(s)
if sLen == 0 {
return true
}
s = strings.ToLower(s)
i := 0
j := sLen - 1
for i <= j {
if !(('a' <= s[i] && s[i] <= 'z') || ('0' <= s[i] && s[i] <= '9')) {
i++
continue
}
if !(('a' <= s[j] && s[j] <= 'z') || ('0' <= s[j] && s[j] <= '9')) {
j--
continue
}
if s[i] != s[j] {
return false
}
i++
j--
}
return true
}
rust
/*
* @Description:
* @Version: 2.0
* @Author: kingeasternsun
* @Date: 2021-03-16 14:29:53
* @LastEditors: kingeasternsun
* @LastEditTime: 2021-03-16 14:53:06
* @FilePath: /125isPalindrome/is_palindrome/src/lib.rs
*/
pub struct Solution;
impl Solution {
pub fn is_palindrome1(s: String) -> bool {
let b = s.into_bytes();
let mut i = 0;
let mut j = b.len()-1;
while i<j {
//跳过非字母或数字
while i<j && (!b[i].is_ascii_alphanumeric()) {i+=1;};
//跳过非字母或数字
while i<j && (!b[j].is_ascii_alphanumeric()) {j-=1;};
if i<j && b[i].to_ascii_uppercase()!=b[j].to_ascii_uppercase(){
return false
}
//由于 j 是usize，所以j有可能变为0，然后 j-=1 后溢出
if i ==j {
return true
}
i+=1;
j-=1;
}
true
}
//更巧妙的写法
pub fn is_palindrome(s: String) -> bool {
let b = s.into_bytes();
let mut i = 0;
let mut j = b.len()-1;
while i<j {
//跳过非字母或数字
if !b[i].is_ascii_alphanumeric() {i+=1;continue;};
//跳过非字母或数字
if !b[j].is_ascii_alphanumeric() {j-=1;continue;};
if b[i].to_ascii_uppercase()!=b[j].to_ascii_uppercase(){
return false
}
i+=1;
j-=1;
}
true
}
}
#[cfg(test)]
mod tests {
use crate::Solution;
#[test]
fn it_works() {
assert_eq!(Solution::is_palindrome("A man, a plan, a canal: Panama".to_string()),true);
assert_eq!(Solution::is_palindrome(String::from("race a car")),false);
assert_eq!(Solution::is_palindrome(String::from("a.")),true);
assert_eq!(Solution::is_palindrome(String::from(".")),true);
}
}
125. 验证回文串
双指针暴力解就好，双百解法
func isPalindrome(s string) bool {
var b1, b2 byte
for i, j := 0, len(s)-1; i<j; i, j = i+1, j-1 {
for ;i<j && (s[i]<'a' || s[i]>'z') && (s[i]<'A' || s[i]>'Z') && (s[i]<'0' || s[i]>'9'); i++ {}
for ;i<j && (s[j]<'a' || s[j]>'z') && (s[j]<'A' || s[j]>'Z') && (s[j]<'0' || s[j]>'9'); j-- {}
if (s[i]>='A' && s[i]<='Z') {
b1 = 'a' + s[i] - 'A'
} else {
b1 = s[i]
}
if (s[j]>='A' && s[j]<='Z') {
b2 = 'a' + s[j] - 'A'
} else {
b2 = s[j]
}
if b1 != b2 {
return false
}
}
return true
}
func needCheck(c byte) bool {
return (c >= 'A' && c <= 'Z') ||
(c >= 'a' && c <= 'z') ||
(c >= '0' && c <= '9')
}
func getVal(c byte) int {
if c >= 'A' && c <= 'Z' {
return int(c - 'A') + 1000
}
if c >= 'a' && c <= 'z' {
return int(c - 'a') + 1000
}
return int(c - '0')
}
func isPalindrome(s string) bool {
n := len(s)
i, j := 0, n-1
for i < j {
for i < j && !needCheck(s[i]) {
i++
}
for i < j && !needCheck(s[j]) {
j--
}
if i >= j {
break
}
if getVal(s[i]) != getVal(s[j]) {
return false
}
i++
j--
}
return true
}
// CreateTime: 2021-03-04 10:15:43
class Solution {
public:
bool isPalindrome(string s) {
int l = 0;
int r = s.size()-1;
while (l < r) {
while (l < r && !isOk(s[l])) {
l++;
}
while (l < r && !isOk(s[r])) {
r--;
}
if (l < r && !isEqual(s[l], s[r])) {
return false;
}
l++;
r--;
}
return true;
}
bool isEqual(char c1, char c2) {
if (isNum(c1) && isNum(c2)) {
return c1 == c2;
} else if (isNum(c1) || isNum(c2)) {
return false;
}
int s1 = 0;
int s2 = 0;
if (isUpper(c1)) {
s1 = c1 - 'A';
} else {
s1 = c1 - 'a';
}
if (isUpper(c2)) {
s2 = c2 - 'A';
} else {
s2 = c2 - 'a';
}
return s1 == s2;
}
bool isOk(char c) {
return isNum(c) || isLower(c) || isUpper(c);
}
bool isNum(char c) {
return '0' <= c && c <= '9';
}
bool isLower(char c) {
return 'a' <= c && c <= 'z';
}
bool isUpper(char c) {
return 'A' <= c && c <= 'Z';
}
};
回溯
func partition(s string) [][]string {
ans := make([][]string, 0)
var backTrace func(str string, arr []string)
backTrace = func(str string, arr []string) {
if len(str) == 0 {
temp := make([]string, len(arr))
copy(temp, arr)
ans = append(ans, temp)
return
}
for i:=0; i<len(str); i++ {
if check(str[:i+1]) {
arr = append(arr, str[:i+1])
backTrace(str[i+1:], arr)
arr = arr[:len(arr)-1]
}
}
}
backTrace(s, []string{})
return ans
}
func check(s string) bool {
for i, j := 0, len(s)-1; i<j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
func partition(s string) [][]string {
n := len(s)
is := make([][]bool, n)
ans := make([][]string, 0)
for i := 0; i < n; i++ {
is[i] = make([]bool, n)
is[i][i] = true
}
for l := 2; l <= n; l++ {
for i := 0; i + l - 1 < n; i++ {
j := i + l - 1
if i + 1 > j - 1 {
is[i][j] = s[i] == s[j]
} else {
is[i][j] = is[i+1][j-1] && (s[i] == s[j])
}
}
}
var dfs func(p int, r []string)
dfs = func(p int, r []string) {
if p >= n {
rr := make([]string, len(r))
copy(rr, r)
ans = append(ans, rr)
return
}
for i := p; i < n; i++ {
if is[p][i] {
r = append(r, s[p:i+1])
dfs(i+1, r)
r = r[:len(r)-1]
}
}
}
dfs(0, nil)
return ans
}
// CreateTime: 2021-03-10 21:00:18
class Solution {
public:
int longestPalindromeSubseq(string s) {
int len = s.size();
vector<vector<int>> f(len+1, vector<int>(len+1));
for (int i = len-1; i >= 0; i--) {
f[i][i] = 1;
for (int j = i+1; j < len; j++) {
if (s[i] == s[j]) {
f[i][j] = f[i+1][j-1]+2;
} else {
f[i][j] = max(f[i][j-1], f[i+1][j]);
}
}
}
return f[0][len-1];
}
};
131
go
// 131. 分割回文串 https://leetcode-cn.com/problems/palindrome-partitioning/
func partition(s string) [][]string {
curList := make([]string, 0)
result := make([][]string, 0)
dfs(curList, s, &result)
return result
}
/*
dfs 没想到没有超时 8ms 5.3MB
*/
func dfs(curList []string, left string, result *[][]string) {
if left == "" {
// tmp := make([]string, len(curList))
// copy(tmp, curList)
curList = append(curList[:0:0], curList...) //https://github.com/go101/go101/wiki/How-to-perfectly-clone-a-slice%3F
*result = append(*result, curList)
return
}
for i := range left {
if ispalindrome(left[:i+1]) {
// golang的代码优势就在 这里 curList通过append传入后，传入的是一个新的slice，不会影响当前的 curList，无需回溯
dfs(append(curList, left[:i+1]), left[i+1:], result)
}
}
return
}
func ispalindrome(s string) bool {
count := len(s)
if count == 1 {
return true
}
for i := 0; i < count/2; i++ {
if s[i] != s[count-i-1] {
return false
}
}
return true
}
336
/*
1. 提前处理，记录每个单词的各个前缀 ，各个后缀是不是回文
2. 对于每个单词，如果某个前缀是回文，就判断这个单词除去前缀后剩下的部分是否和其他单词对称
3. 对于每个单词，如果某个后缀是回文，就判断这个单词除去后缀后剩下的部分是否和其他单词对称
*/
func palindromePairs(words []string) [][]int {
//判断某个单词的某个区间是否是回文
judgePali := func(i, beg, end int) bool {
for beg < end {
if words[i][beg] != words[i][end] {
return false
}
beg++
end--
}
return true
}
//预处理，提前记录每个单词的逆序的map
reverseMap := make(map[string]int, 0)
preMap := make(map[int][]int, 0) //记录每个单词哪些前缀是回文
suffMap := make(map[int][]int, 0) //记录每个单词哪些后缀是回文
for i, w := range words {
reverseMap[reverse(w)] = i
for j := 0; j < len(w); j++ {
if judgePali(i, 0, j) {
preMap[i] = append(preMap[i], j)
}
if judgePali(i, j, len(w)-1) {
suffMap[i] = append(suffMap[i], j)
}
}
}
res := make([][]int, 0)
for i, w := range words {
if j, ok := reverseMap[w]; ok {
if i > j {
res = append(res, []int{i, j})
res = append(res, []int{j, i})
}
}
//对于回文的每个前缀
for _, endID := range preMap[i] {
//判断剩下的部分是否存在 反向的单词
if j, ok := reverseMap[(w[endID+1:])]; ok {
res = append(res, []int{j, i})
}
}
//对于回文的每个后缀
for _, endID := range suffMap[i] {
//判断剩下的部分是否存在 反向的单词
if j, ok := reverseMap[(w[:endID])]; ok {
res = append(res, []int{i, j})
}
}
}
return res
}
func reverse(s string) string {
res := make([]byte, len(s))
for i := 0; i < len(s); i++ {
res[len(s)-i-1] = s[i]
}
return string(res)
}
516
//最长公共子序列的问题
func longestPalindromeSubseq(s string) int {
if len(s) <= 1 {
return len(s)
}
num := len(s)
dp := make([][]int, num+1)
for i := 0; i <= num; i++ {
dp[i] = make([]int, num+1)
}
for i := num; i > 0; i-- {
for j := i; j <= num; j++ {
if i == j {
dp[i][j] = 1
continue
}
if s[i-1] == s[j-1] {
dp[i][j] = dp[i+1][j-1] + 2
} else {
dp[i][j] = max(dp[i][j-1], dp[i+1][j])
}
}
}
return dp[1][num]
}
func max(i, j int) int {
if i > j {
return i
}
return j
}
func nextPalindrome(nums *[]int) int {
n := len(*nums)
(*nums)[(n-1)/2]++
for i := (n-1)/2; i >=0; i-- {
if (*nums)[i] ==10{
if i ==0{
*nums = append(*nums, 1)
(*nums)[i]=1
}else {
(*nums)[i]=0
(*nums)[i-1]++
}
(*nums)[n-1-i]=0
}else {
(*nums)[n-1-i]=(*nums)[i]
break
}
}
temp := 0
for i := 0; i < len(*nums); i++ {
temp=temp *10+(*nums)[i]
}
return temp
}
func Prime(n int) bool {
if n <=2{
return n==2
}
if n &1==0{
return false
}
for i := 3; i*i <= n; i+=2 {
if n %i ==0{
return false
}
}
return true
}
func primePalindrome(n int) int {
var nums []int
temp :=n
for temp != 0 {
nums = append(nums, temp%10)
temp /= 10
}
for i := 0; i < len(nums); i++ {
nums[i]=nums[len(nums)-1-i]
}
temp = 0
for i := 0; i < len(nums); i++ {
temp=temp *10+nums[i]
}
for n < 2e8 {
if temp >=n && Prime(temp){
break
}
temp = nextPalindrome(&nums)
}
return temp
}
func isPrime(x int) bool {
if x == 2 {
return true
}
if x%2 == 0 {
return false
}
for i := 3; i*i <= x; i += 2 {
if x%i == 0 {
return false
}
}
return true
}
func base(x int) int {
r := 1
for x >= r {
r *= 10
}
return r
}
func calc1(x int) int {
xx, yy := x, 0
for x > 0 {
yy = yy*10 + x%10
x /= 10
}
return xx*base(xx) + yy
}
func calc2(x, d int) int {
xx, yy := x, 0
for x > 0 {
yy = yy*10 + x%10
x /= 10
}
bs := base(xx)
return xx*bs*10 + d*bs + yy
}
func minInt(a, b int) int {
if a < b {
return a
}
return b
}
func primePalindrome(N int) int {
ans := int(1e8 * 2)
for i := 2; i < 10; i++ {
if i >= N && isPrime(i) {
return i
}
}
haha:
for i := 1; i <= 1999; i++ {
for j := 0; j < 10; j++ {
xx := calc2(i, j)
if xx >= N && isPrime(xx) {
ans = minInt(ans, xx)
break haha
}
}
}
for i := 1; i <= 9999; i++ {
xx := calc1(i)
if xx > ans {
return ans
}
if xx >= N && isPrime(xx) {
ans = minInt(ans, xx)
break
}
}
return ans
}
func maxInt(a, b int) int {
if a > b {
return a
}
return b
}
func check(x int64) bool {
xx, y := x, int64(0)
for xx > 0 {
y = y*10 + xx%10
xx /= 10
}
return x == y
}
func base(x int64) int64 {
bs := int64(1)
for bs <= x {
bs *= 10
}
return bs
}
func reverse(x int64) int64 {
y := int64(0)
for x > 0 {
y = y * 10 + x % 10
x /= 10
}
return y
}
func calc(limit int64) int64 {
cnt := int64(0)
//
for i := int64(1); i < 10 && i*i <= limit; i++ {
if check(i*i) {
cnt++
}
}
// 10^4 x 10^4
for i := int64(1); i <= 10000; i++ {
bs := base(i)
rr := reverse(i)
for j := int64(0); j < 10; j++ {
xx := i*bs*10 + j * bs + rr
if xx*xx > limit {
break
}
if check(xx*xx) {
cnt++
}
}
}
// 10^4 10^4
for i := int64(1); i <= 33333; i++ {
xx := i * base(i) + reverse(i)
if xx*xx > limit {
break
}
if check(xx*xx) {
cnt++
}
}
return cnt
}
func superpalindromesInRange(left string, right string) int {
leftI, _ := strconv.ParseInt(left, 10, 64)
rightI, _ := strconv.ParseInt(right, 10, 64)
ans := calc(rightI)
if leftI - 1 > 0 {
ans -= calc(leftI-1)
}
return int(ans)
}
// 马拉车。。。
func longestPalindrome(s string) string {
start, end := 0, -1
t := “#”
for i := 0; i < len(s); i++ {
t += string(s[i]) + “#”
}
t += “#”
s = t
arm_len := []int{}
right, j := -1, -1
for i := 0; i < len(s); i++ {
var cur_arm_len int
if right >= i {
i_sym := j * 2 - i
min_arm_len := min(arm_len[i_sym], right-i)
cur_arm_len = expand(s, i-min_arm_len, i+min_arm_len)
} else {
cur_arm_len = expand(s, i, i)
}
arm_len = append(arm_len, cur_arm_len)
if i + cur_arm_len > right {
j = i
right = i + cur_arm_len
}
if cur_arm_len * 2 + 1 > end - start {
start = i - cur_arm_len
end = i + cur_arm_len
}
}
ans := “”
for i := start; i <= end; i++ {
if s[i] != ‘#’ {
ans += string(s[i])
}
}
return ans
}
func expand(s string, left, right int) int {
for ; left >= 0 && right < len(s) && s[left] == s[right]; left, right = left-1, right+1 { }
return (right - left - 2) / 2
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
各位大佬看看哪错了
func longestPalindrome(s string) string {
res := ""
for i := 0; i < len(s); i++ {
for l,r := i,i; l >= 0 && r < len(s) && s[l] == s[r]; l, r = l-1, r+1 {
if len(res) < r-l+1 {
res = s[l : r-l+1]
}
}
for l,r := i,i+1; l >= 0 && r < len(s) && s[l] == s[r]; l, r = l-1, r+1 {
if len(res) < r-l+1 {
res = s[l : r-l+1]
}
}
}
return res
}
请教暴力写法：大佬看看怎么修改
func longestPalindrome(s string) string {
res := ""
for i := 0; i < len(s); i++ {
for l,r := i,i; l >= 0 && r < len(s) && s[l] == s[r]; l, r = l-1, r+1 {
if len(res) < r-l+1 {
res = s[l : r-l+1]
}
}
for l,r := i,i+1; l >= 0 && r < len(s) && s[l] == s[r]; l, r = l-1, r+1 {
if len(res) < r-l+1 {
res = s[l : r-l+1]
}
}
}
return res
}
res = s[l :r+1] 这样试试。切片用法理解错了。思路是对的。