leetcode 680. 验证回文字符串 Ⅱ
题目：680. 验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例1:
输入: “aba”
输出: True
示例2:
输入: “abca”
输出: True
解释: 你可以删除c字符。
注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
方法一：双指针（对撞指针）
思路：双指针（对撞指针） ，一个从头向尾遍历，一个指针从尾向头遍历，循环一次头指针向后移一位，尾指针向前一位。若找到头指针指向的字符不等于尾指针指向的字符时，分为两种情况，一种是删除左指针指向字符，然后再次使用双指针（对撞指针）算法进行遍历判断是否是回文字符串，另一种是删除右指针指向字符，然后再次使用双指针（对撞指针）算法进行遍历判断是否是回文字符串，当有一种情况判断出是回文串时，即为回文字符串。若遍历结束还没有找到头指针指向的字符不等于尾指针指向的字符，即为回文字符串。
运行数据：执行用时：7 ms，内存消耗：40.1 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
public boolean validPalindrome(String s) {
int i = 0, j = s.length() - 1;
while (i < j) {
if (s.charAt(i) != s.charAt(j)) {
if (s.charAt(i + 1) == s.charAt(j)) {
int l = i + 1, r = j;
boolean flag = true;
while (l < r) {
if (s.charAt(l) != s.charAt(r)) {
flag = false;
break;
} else {
l++;
r--;
}
}
if (flag) {
return true;
}
}
if (s.charAt(i) == s.charAt(j - 1)) {
int l = i, r = j - 1;
boolean flag = true;
while (l < r) {
if (s.charAt(l) != s.charAt(r)) {
flag = false;
break;
} else {
l++;
r--;
}
}
if (flag) {
return true;
}
}
return false;
} else {
i++;
j--;
}
}
return true;
}
|
方法二：双指针（对撞指针）简洁版
思路：思路一的简洁版，代码简洁，但执行速度有所下降
运行数据：执行用时：9 ms，内存消耗：39.9 MB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
public boolean validPalindrome(String s) {
for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return isPalindrome(i + 1, j, s) || isPalindrome(i, j - 1, s);
}
}
return true;
}
public boolean isPalindrome(int i, int j, String s) {
for (; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
|
相关链接：
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
