# 回文串
回文的概念就是一个序列正着来倒着来是一样的,比如回文数字 12321
,回文字符串 abbccdccbba
,诸如此类。
# 判断是否是回文串
一般就是两头对比
public boolean isPalindrome(String s) { | |
int len = s.length(); | |
for (int i = 0; i < len; i++) { | |
if (s.charAt(i) != s.charAt(len - i - 1)){ | |
return false; | |
} | |
} | |
return true; | |
} | |
// 或者 | |
public boolean isPalindrome(String s) { | |
int len = s.length(); | |
int i = 0; | |
int j = len -1; | |
while(i < j){ | |
if(s.charAt(i) != s.charAt(j)){ | |
return false; | |
} | |
i++; | |
j--; | |
} | |
return true; | |
} |
使用 StringBuffer 反转后比较
public boolean isPalindrome(String s) { | |
return new StringBuffer(str).reverse().toString().equals(str); | |
} |
# 题目
# 简单难度
# 验证回文串
[125. 验证回文串][https://leetcode.cn/problems/valid-palindrome/]
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串
s
,如果它是 回文串 ,返回true
;否则,返回false
。
class Solution { | |
public boolean isPalindrome(String s) { | |
// 去除非字母数字的字符 | |
s = s.replaceAll("[^a-zA-Z0-9]", ""); | |
// 全部转换为小写 | |
s = s.toLowerCase(); | |
// 字符串翻转比较 | |
return new StringBuffer(s).reverse().toString().equals(s); | |
} | |
} |
# 验证回文串 II
680. 验证回文串 II
给你一个字符串
s
,最多 可以从中删除一个字符。请你判断
s
是否能成为回文字符串:如果能,返回true
;否则,返回false
。
思路: 双指针
- 考虑到只能删除一个,查找到第一对不相等的字符的时候会有两种情况。
- 删除左侧的字符,删除右侧的字符。
- 所以会有两个分支判断
- 如果这个字符串符合题目的要求,那么删除后的字符串一定是回文的。
- 当比较到第一对不相等的字符位置时,只需要考虑删除后的子串是否是回文的就行。
class Solution { | |
public boolean validPalindrome(String s) { | |
int len = s.length(); | |
boolean flag = true; | |
int i = 0; | |
int j = len -1; | |
while(i < j){ | |
if(s.charAt(i) != s.charAt(j)){ | |
return jud(s.substring(i+1, j+1)) || jud(s.substring(i, j)); | |
}else { | |
i++; | |
j--; | |
} | |
} | |
return true; | |
} | |
boolean jud(String str){ | |
return new StringBuffer(str).reverse().toString().equals(str); | |
} | |
} |
注意: subString
方法在取字符串时左闭右开, [a,b)
# 回文数
9. 回文数
给你一个整数
x
,如果x
是一个回文整数,返回true
;否则,返回false
。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
- 例如,
121
是回文,而123
不是。-121
, 从右向左读,为121-
。因此它不是一个回文数。
思路:
- 首先排除负数
- 以若干连续 0 结尾的数也不是回文的
# 直接数转化字符串
class Solution { | |
public boolean isPalindrome(int x) { | |
// 负数直接拜拜 | |
if (x < 0 || (x % 10 == 0 && x != 0)) { | |
return false; | |
} | |
String str = x + ""; | |
int len = str.length(); | |
// return new StringBuffer(str).reverse().toString().equals(str); | |
for (int i = 0; i < len; i++) { | |
if (str.charAt(i) != str.charAt(len - i - 1)){ | |
return false; | |
} | |
} | |
return true; | |
} | |
} |
# 使用数字解决,可以使用折半思想
class Solution { | |
public boolean isPalindrome(int x) { | |
// 思考:这里大家可以思考一下,为什么末尾为 0 就可以直接返回 false | |
if (x < 0 || (x % 10 == 0 && x != 0)) return false; | |
int revertedNumber = 0; | |
// 翻转到一般就行 | |
while (x > revertedNumber) { | |
revertedNumber = revertedNumber * 10 + x % 10; | |
x /= 10; | |
} | |
// 考虑数字的位数是奇数和偶数 | |
return x == revertedNumber || x == revertedNumber / 10; | |
} | |
} |
# 最长回文串 - 简单
给一个包含大写字母和小写字母的字符串
s
,返回 这些字母构造成的 最长的回文串 。在构造过程中,请注意 区分大小写 。比如
"Aa"
不能当做一个回文字符串。
思路:
- 题目问的是这些字母拼成的字符串,只需要考虑各个字母的数量即可
- 根据各个字母的数量的奇偶,有两种情况
- 回文串字符数量为奇数,用了一个奇数数量的字母
- 回文串字符数量为偶数,所有字母的数量都为偶数
- 开一个数组存各个字符数量
- 第一个奇数数量的字符可以全部加到回文串中
- 之后的字符数量只能为偶数加入回文串
class Solution { | |
public int longestPalindrome(String s) { | |
int[] count = new int[60]; | |
for (char ch : s.toCharArray()) { | |
count[ch - 'A']++; | |
} | |
int res = 0; | |
boolean flag = true; | |
for (int i = 0; i < 60; i++) { | |
if((count[i] & 1) == 1 && flag){ | |
res++; | |
flag = false; | |
} | |
res += ((count[i] >> 1) << 1); | |
} | |
return res; | |
} | |
} |
使用 Java 的流进行优化一下
public int longestPalindrome(String s) { | |
Map<Integer, Integer> count = s.chars().boxed() | |
.collect(Collectors.toMap(k -> k, v -> 1, Integer::sum)); | |
int ans = count.values().stream().mapToInt(i -> i - (i & 1)).sum(); | |
return ans < s.length() ? ans + 1 : ans; | |
} |
# 回文链表
234. 回文链表
给你一个单链表的头节点
head
,请你判断该链表是否为回文链表。如果是,返回true
;否则,返回false
。
折半思想,使用快慢指针找到中间节点,之后的链表翻转,最后比较就行
/** | |
* Definition for singly-linked list. | |
* public class ListNode { | |
* int val; | |
* ListNode next; | |
* ListNode() {} | |
* ListNode(int val) { this.val = val; } | |
* ListNode(int val, ListNode next) { this.val = val; this.next = next; } | |
* } | |
*/ | |
class Solution { | |
public boolean isPalindrome(ListNode head) { | |
ListNode mid = midNode(head); | |
ListNode cmp = reverseList(mid); | |
while (head != null && cmp != null) { | |
if(head.val != cmp.val){ | |
return false; | |
} | |
head = head.next; | |
cmp = cmp.next; | |
} | |
return true; | |
} | |
private ListNode midNode(ListNode head){ | |
ListNode slow = head; | |
ListNode fast = head; | |
while (fast != null && fast.next != null){ | |
slow = slow.next; | |
fast = fast.next.next; | |
} | |
return slow; | |
} | |
private ListNode reverseList(ListNode mid) { | |
ListNode pre = null; | |
ListNode cur = mid; | |
while(cur !=null) { | |
ListNode next = cur.next; | |
cur.next = pre; | |
pre = cur; | |
cur = next; | |
} | |
return pre; | |
} | |
} |
# 中等难度
# 最长回文子串
5. 最长回文子串
给你一个字符串
s
,找到s
中最长的回文子串。如果字符串的反序与原始字符串相同,则该字符串称为回文字符串。
暴力的话会超时,可以用中心扩散法或动态规划
# 中心扩散法
思路:
- 遍历,选择一个元素
i
- 两个指针,从元素左
left = i-1
右right = i+1
开始比较- 如果左指针元素与
i
位置元素相等,左指针左移,否则不变 - 右指针同理,右移
- 之后比较两指针所指元素
- 上述过程的好处是泛化了回文串的字符奇数偶数问题,使得该方法适用
- 如果左指针元素与
- 每次选择中间元素
i
记录最大长度和起始位置即可。
public String longestPalindrome(String s) { | |
if (s == null || s.length() == 0) { | |
return ""; | |
} | |
int strLen = s.length(); | |
int left = 0; | |
int right; | |
int len; | |
int maxStart = 0; | |
int maxLen = 0; | |
for (int i = 0; i < strLen; i++) { | |
left = i - 1; | |
right = i + 1; | |
len = 1; | |
while (left >= 0 && s.charAt(left) == s.charAt(i)) { | |
len++; | |
left--; | |
} | |
while (right < strLen && s.charAt(right) == s.charAt(i)) { | |
len++; | |
right++; | |
} | |
while (left >= 0 && right < strLen &&s.charAt(right) == s.charAt(left)) { | |
len = len + 2; | |
left--; | |
right++; | |
} | |
if (len > maxLen) { | |
maxLen = len; | |
maxStart = left; | |
} | |
} | |
return s.substring(maxStart + 1, maxStart + maxLen + 1); | |
} |
# 动态规划
适用动态规划,首先要想状态转移,对于回文串,我们可以认为回文串的状态转移是从头尾向中间走。
定义状态,使用
dp[i][j]
记录子串[i,j]
是否回文状态转移方程:首先要
s[i] == s[j]
,其次是dp[i-1][j+1] == true
注意
i - 1 != j + 1
,所以要求子串长度大于等于 2dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
public String longestPalindrome(String s) { | |
if (s == null || s.length() < 2) { | |
return s; | |
} | |
int strLen = s.length(); | |
int maxStart = 0; // 最长回文串的起点 | |
int maxLen = 1; // 最长回文串的长度 | |
boolean[][] dp = new boolean[strLen][strLen]; | |
for (int r = 1; r < strLen; r++) { | |
for (int l = 0; l < r; l++) { | |
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) { | |
dp[l][r] = true; | |
if (r - l + 1 > maxLen) { | |
maxLen = r - l + 1; | |
maxStart = l; | |
} | |
} | |
} | |
} | |
return s.substring(maxStart, maxStart + maxLen); | |
} |