【剑指 Offer II 019. 最多删除一个字符得到回文】

我就是我 2023-09-26 17:10 21阅读 0赞

package com.example.demomain.demoleetcode.easy;
    
    /**
     * 给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
     *
     * 示例 1:
     *
     * 输入: s = "aba"
     * 输出: true
     * 示例 2:
     *
     * 输入: s = "abca"
     * 输出: true
     * 解释: 可以删除 "c" 字符 或者 "b" 字符
     * 示例 3:
     *
     * 输入: s = "abc"
     * 输出: false
     * 提示:
     *
     * 1 <= s.length <= 105
     * s 由小写英文字母组成
     * @author Administrator
     */
    public class ValidPalindrome {
        
    
        /**
         * 双指针
         *
         * @param s
         * @return
         */
        public boolean validPalindrome(String s) {
        
            // true：还没有删除字符
            return check(s, 0, s.length() - 1, true);
        }
    
        public boolean check(String s, int left, int right, boolean flag) {
        
            while (left < right) {
        
                if (s.charAt(left) != s.charAt(right)) {
        
                    if (flag) {
        
                        // 还没有删除，可以删除右边或去掉左边成立即可，flag为false，后续不能再删除
                        return check(s, left, right - 1, false)
                                || check(s, left + 1, right, false);
                    } else {
        
                        // 已经删除了一个字符，由于只能删除一个，则 false
                        return false;
                    }
                }
                left++;
                right--;
            }
            return true;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指 Offer 14- II. 剪绳子 II

算法其本质就是通过合适的数据结构和数学运算来解决相应的问题，今天遇到一个完美的将数学运算结合进来的题目，话不多说直接看题：题目描述： > 给你一根长度为 n 的绳子，请把

布满荆棘的人生/ 2023年10月11日 17:32/ 0 赞/ 139 阅读

相关【剑指 Offer II 019. 最多删除一个字符得到回文】

package com.example.demomain.demoleetcode.easy; / 给定一个非空字符串 s，请判断如果最

我就是我/ 2023年09月26日 17:10/ 0 赞/ 22 阅读

相关【剑指 Offer II 018. 有效的回文】

package com.example.demomain.demoleetcode.easy; import org.junit.Test;

╰半橙微兮°/ 2023年09月26日 17:09/ 0 赞/ 32 阅读

相关剑指offer算法题019：顺时针打印矩阵

小编在求职找找工作期间剑指offer上的算法题刷了很多遍，并且每道题小编当时都总结了一种最适合面试时手撕算法的最优解法。考虑到剑指offer算法题在面试中的高频出现，小编每天和

Myth丶恋晨/ 2023年02月20日 13:47/ 0 赞/ 35 阅读

相关剑指offer | 14. II. 剪绳子

题目内容 > 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 > k\[0\],k\[1\]…k\[m

喜欢ヅ旅行/ 2022年12月25日 05:58/ 0 赞/ 282 阅读

相关剑指 Offer 14- II. 剪绳子 II

题目给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m - 1\]

朴灿烈づ我的快乐病毒、/ 2022年12月17日 05:58/ 0 赞/ 252 阅读

相关剑指 Offer 14- II. 剪绳子 II

题目：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k\[0\],k\[1\]…k\[m - 1\]

- 日理万妓/ 2022年12月07日 12:18/ 0 赞/ 266 阅读

相关剑指offer 14 剪绳子 II

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

红太狼/ 2022年11月06日 03:59/ 0 赞/ 277 阅读

相关剑指Offer II --- 2021/9/2

目录剑指Offer II 116. 朋友圈剑指Offer II 098. 路径的数目剑指Offer II 068. 查找插入位置剑指Off

一时失言乱红尘/ 2022年09月09日 14:53/ 0 赞/ 212 阅读

相关剑指Offer II --- 2021/9/1

目录剑指Offer II 012. 左右两边子数组的和相等剑指Offer II 015. 字符串中的所有变位词剑指Offer II 018. 有效

短命女/ 2022年09月09日 12:45/ 0 赞/ 214 阅读