680. 验证回文字符串 Ⅱ

小鱼儿 2022-12-07 12:13 146阅读 0赞

# 题目： #

[680. 验证回文字符串 Ⅱ][680. _]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]

# 题解：双指针 #

[125. 验证回文串][125.]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][2020091517505085.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 9]

# 代码：双指针 #

public class code680 { 
    
    // 思路： 判断是否是回文串，只要存在一个不相同，即不为回文串;
    // 删除一个字符串的方法：① 删除左边的 ②删除右边的
    // 删除之后只需要判断没判断过的部分，不需要重新开始了喔！！
    
        public static boolean validPalindrome(String s) { 
            // 不用判断边界
            int i = 0;
            // 越界问题呀 大兄弟！！！
            int j = s.length() - 1;
            while(i < j)
            { 
                // 碰到要删的节点
                if(s.charAt(i) != s.charAt(j)) // 不相同，删掉一个字符串，分别判断是不是回文串，取或（有一个是，说明往那边删就对了）
                { 
                    // 分两种情况，一是右边减一，二是左边加一
                    return isPalindrome(s, i, j - 1) || isPalindrome(s, i + 1, j);
                }
                i++;
                j--;
            }
            return true; // 最多删一个, 咱不删也成
        }
    
        public static boolean isPalindrome(String s, int i, int j)
        { 
            while(i < j)
            { 
                if(s.charAt(i) != s.charAt(j))
                { 
                    return false; // 你咋又不相同了呢！
                }
                // 记得循环递归啊，别死跑啊
                i++;
                j--;
            }
            return true;
        }
    
        public static void main(String[] args) { 
            String s1 = "aba";
            boolean res1 = validPalindrome(s1);
            System.out.println(res1);
    
            String s2 = "abca";
            boolean res2 = validPalindrome(s2);
            System.out.println(res2);
        }
    }

# 参考： #

1.  [验证回文字符串 Ⅱ][Link 1]
2.  [从两侧向中间找到不等的字符，删除后判断是否回文][Link 2]
3.  [java双指针（简单易懂）][java]
4.  [图解】双指针 O(N) 时间复杂度][O_N_]

[680. _]: https://leetcode-cn.com/problems/valid-palindrome-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/118ecb442c1941f8b3fbe89817503d9f.png
[125.]: https://blog.csdn.net/zyx_ly/article/details/108602724
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/2f20945c9ba34e73ab53919dc326555e.png
[2020091517505085.png_pic_center]: /images/20221123/b2090d9edf0941839f32b028d26fb60b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/3d66c8202abd455d866e94ec45858a03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/3b65b7a479b04276a5aa6d4e7346e7ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/e9c2aa5f1fc1477489ac84117e774525.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/87c82947a32d4cb78391663225f449fe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/80cafceaf84a4c5b924f7e89a538b59f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/38fc7e4d450040f397d399f8e87d8910.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/ad9e44d0672f478eb2b1b0d21caa491d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3p5eF9seQ_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/6261d37259e14bd1b2be985dce1e9175.png
[Link 1]: https://leetcode-cn.com/problems/valid-palindrome-ii/solution/yan-zheng-hui-wen-zi-fu-chuan-ii-by-leetcode-solut/
[Link 2]: https://leetcode-cn.com/problems/valid-palindrome-ii/solution/cong-liang-ce-xiang-zhong-jian-zhao-dao-bu-deng-de/
[java]: https://leetcode-cn.com/problems/valid-palindrome-ii/solution/javashuang-zhi-zhen-jian-dan-yi-dong-by-cui-dan/
[O_N_]: https://leetcode-cn.com/problems/valid-palindrome-ii/solution/shuang-zhi-zhen-on-shi-jian-fu-za-du-by-cyc2018-2/