680. Valid Palindrome II (Easy)

Tony.Xu 收录于题解

2020-06-16 约 507 字预计阅读 2 分钟次阅读

LeetCode

回文字符串

想法

核心逻辑

判断回文，即判断位置 i 与 length - i 的值是否相等
支持删除一次，即需要判断左删一次与右删一次的情况

特殊处理

如果左删失败，要尝试进行右删（需要读档点或递归调用）

调试记录

"lcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupucul"

这个测试用例失败了好几次，因一开始太长，看着太混乱，所以缩小了下，

"lcupuufxoohdfpggpfdhooxfuupucul"

然后手动模拟，发现存在一个点同时能够左删和右删，且左删不是回文，右删才是。

说明自己考虑这个问题的时候没有考虑全面

测试数据

“abc” “aaa” “abba” “abcba” “aaaaabbbbbaaaaab” “lcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupucul”

AC 代码

v 1.0.0

2020年06月16日

 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


/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
    let i = 0;
    let j = s.length - 1;
    let canDelete = true;
    let savePoint = [];
    // 当一个点同时满足左删右删，则记录这个点的信息，即读档点
    // 因题目告知只能删一次，所以读档点也只会有一个
    while(i<=j) {
        if(s[i] !== s[j]) {
            if(savePoint.length !== 0) {
                i = savePoint[0];
                j = savePoint[1];
                savePoint = [];
                continue;
            }
            if(!canDelete) {
               return false;
            }
            canDelete = false;
            // 记录读档点
            if(s[i+1] === s[j] && s[j-1] === s[i]) {
                // 默认从左边尝试，所以读档点总是在右边
                savePoint = [i+1, j-2];
            }
            if(s[i+1] === s[j] ) {
                // 优先尝试删除左边
                i = i + 2;
                j--;
                continue;
            }
            if(s[j-1] === s[i] ) {
                // 左边不满足，尝试删除右边
                j = j-2;
                i++;
                continue;
            }
            // 尝试失败
            return false;
        }
        if(i === j) {
            // 奇数最后相遇时
            return true;
        }
        i++;
        j--;
    }
    // 偶数情况，i>j，返回true
    return true;
};

目录