算法 系列博客

【算法】刷题范围建议 和 代码规范
【算法】复杂度理论 ( 时间复杂度 )

【字符串】最长回文子串 ( 蛮力算法 )
【字符串】最长回文子串 ( 中心线枚举算法 )
【字符串】最长回文子串 ( 动态规划算法 ) ★
【字符串】字符串查找 ( 蛮力算法 )
【字符串】字符串查找 ( Rabin-Karp 算法 )

【算法】双指针算法 ( 双指针算法分类 | 相向双指针 | 有效回文串 )
【算法】双指针算法 ( 有效回文串 II )

一、有效回文串 II

有效回文串 II : https://www.lintcode.com/problem/891/

给定非空字符串 , 最多删除一个字符 , 判断是否可以将该字符串变成回文串 ;

该算法是一个贪心算法 , 给定一个字符串 “abca” , 设置两个指针 , 分别指向最左侧字符 和 最右侧字符 , 从两端开始遍历 , 逐个比较两个指针指向的字符是否相等 ;

如果出现了左右指针指向的字符不相等 , 那么只能有两种操作 , 要么删除左指针指向的字符 , 要么删除右指针指向的字符 ;

删除左指针指向的字符 , 继续向后遍历 , 判定整个字符串是否是回文串 ;
删除右指针指向的字符 , 继续向后遍历 , 判定整个字符串是否是回文串 ;

如果上述两种方案 , 都不是回文串 , 那么说明删除单个字符后字符串仍不是回文串 ;

代码示例 :

class Solution {

    /**
     * 给一个非空字符串 s，你最多可以删除一个字符。判断是否可以把它变成回文串。
     * @param s 给定的字符串 
     * @return 删除零个或一个字符后是否是回文串
     */
    public boolean validPalindrome(String s) {
        if (s == null) {
            return false;
        }

        // 先判定该字符串是否是回文串
        // 数组中 0 索引存放左指针, 1 索引存放右指针 
        int[] pointer = new int[2];
        findDifference(s, 0, s.length() - 1, pointer);
        if (pointer[0] >= pointer[1]) {
            return true;
        }

        // 如果字符串不是回文串, 则考虑删除左指针/右指针指向的字符, 再判定是否是字符串
        // 删除左指针指向的字符, 并验证是否是回文串
        return isPalindrome(s, pointer[0] + 1, pointer[1])
        		// 删除右指针指向的字符, 并验证是否是回文串  
                || isPalindrome(s, pointer[0], pointer[1] - 1); 
    }

    private void findDifference(String s, int left, int right, int[] result) {
        // 对比两字符是否相等, 如果相等, 指针向中间移动一位
        while (left < right && s.charAt(left) == s.charAt(right)) {
            left++;
            right--;
        }
        // 设置返回值
        // 如果该字符串是回文串, 则左指针最后等于 ( 偶数个字符 ) 或者大于右指针 ( 奇数个字符 )
        // 如果该字符串不是回文串 , 则左右指针原封不动返回
        result[0] = left;
        result[1] = right;
    }

    private boolean isPalindrome(String s, int left, int right) {
        // 判定 s 字符串是否是回文串
        int[] pointer = new int[2];
        findDifference(s, left, right, pointer);
        return pointer[0] >= pointer[1];
    }
}

class Main {
    public static void main(String[] args) {
        System.out.println(
                new Solution().validPalindrome("abcnba")
        );
    }
}

  

 

  
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
 

文章来源: hanshuliang.blog.csdn.net，作者：韩曙亮，版权归原作者所有，如需转载，请联系作者。

原文链接：hanshuliang.blog.csdn.net/article/details/119088328