LWC 50：680. Valid Palindrome II
LWC 50：680. Valid Palindrome II
用户1147447
发布于 2019-05-26 09:21:04
发布于 2019-05-26 09:21:04
文章被收录于专栏：机器学习入门
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434612
LWC 50：680. Valid Palindrome II
Problem:
Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: “aba” Output: True
Example 2:
Input: “abca” Output: True Explanation: You could delete the character ‘c’.
Note:
The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
判断删除至多一位后是否为回文，很简单，直接从两头开始搜索，如果两头的字符不一致，则需要删除前者或者后者，完成删除后判断剩余字符串是否为回文。
最初版本：
public boolean validPalindrome(String s) {
char[] cs = s.toCharArray();
int n = cs.length;
if (n == 0) return true;
int lf = 0, rt = n - 1;
int cnt = 0;
boolean valid1 = true;
while (lf < rt){
if (cs[lf] == cs[rt]){
lf ++;
rt --;
}
else{
if (cs[lf + 1] == cs[rt]){
lf ++;
cnt++;
}
else if (cs[lf] == cs[rt - 1]){
rt --;
cnt++;
}
else{
valid1 = false;
break;
}
}
}
valid1 = valid1 && cnt <= 1;
boolean valid2 = true;
cnt = 0;
lf = 0;
rt = n - 1;
cnt = 0;
while (lf < rt){
if (cs[lf] == cs[rt]){
lf ++;
rt --;
}
else{
if (cs[lf] == cs[rt - 1]){
rt --;
cnt++;
}
else if (cs[lf + 1] == cs[rt]){
lf ++;
cnt++;
}
else{
valid2 = false;
break;
}
}
}
valid2 = valid2 && cnt <= 1;
return valid1 || valid2;
}精简版本：
public boolean validPalindrome(String s) {
char[] cs = s.toCharArray();
int lf = 0, rt = s.length() - 1;
while (lf < rt) {
if (cs[lf] != cs[rt]) return isPalindrome(cs, lf + 1, rt) || isPalindrome(cs, lf, rt - 1);
lf ++;
rt --;
}
return true;
}
public boolean isPalindrome(char[] cs, int start, int end) {
while (start < end) {
if (cs[start++] != cs[end--]) return false;
}
return true;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2017年09月21日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
