LeetCode每日一练（验证回文字符串 Ⅱ）

快来打我* 2022-08-29 09:45 176阅读 0赞

题目如下：

> 给定一个非空字符串 `s`，**最多**删除一个字符。判断是否能成为回文字符串。

![在这里插入图片描述][9729a291025b40f08355745cd57d7fa6.png]

题目要求规定一个非空字符串，最多删除一个字符，判断是否能称为回文字符串，那么首先就需要考虑给定的字符串是否已经为回文字符串，如果是，则直接返回true；如果不是，还需要去通过删除一个字符来使其成为回文字符串。

既然只允许最多删除一个字符，那么很容易想到的就是暴力穷举法，对于一个给定的字符串，依次从左到右进行删除，判断每次删除后的字符串是否为回文字符串，如果有满足条件的情况，则返回true；如果没有，则返回false。

例如：

![在这里插入图片描述][0f3650d17881487e909680cc6e91dd3a.png]

首先删除字符a，那么原字符串就变为bca，此时判断bca是否为回文字符串：

![在这里插入图片描述][0954bdcdb3ec44cc8bc24268f82bde1c.png]

bca并不是回文字符串，由此继续删除第二个字符b，此时判断aca是否为回文字符串：

![在这里插入图片描述][a8dd30338a1640d9994198dd72bfe148.png]

aca也不是回文字符串，由此继续删除第三个字符c，此时判断aba是否为回文字符串：

![在这里插入图片描述][3f12d51057c9469fb30e7f78ece213d8.png]

aba是回文字符串，程序到这里就可以结束了，返回true。

由此得出代码如下：

public class Solution { 
    
        public static boolean validPalindrome(String s) { 
            // 首先直接判断s是否为回文字符串
            boolean flag = isPdStr(s);
            if (flag) { 
                return true;
            }
            // 若s本身不是回文字符串，则依次删除每个字符
            for (int i = 0; i < s.length(); i++) { 
                String newStr = removeCharAt(s, i);
            // 判断删除后的字符串是否为回文字符串
                flag = isPdStr(newStr);
                if(flag){ 
                    return true;
                }
            }
            return false;
        }
    
        /** * 返回删除指定字符后的字符串 * * @param s * @param pos * @return */
        public static String removeCharAt(String s, int pos) { 
            return s.substring(0, pos) + s.substring(pos + 1);
        }
    
        /** * 判断是否为回文字符串 * * @param s * @return */
        public static boolean isPdStr(String s) { 
            // 反转字符串
            String reverseStr = new StringBuilder(s).reverse().toString();
            return s.equals(reverseStr);
        }
    }

这里共抽取了两个方法用于判断一个字符串是否为回文字符串和获得删除指定字符后的字符串。

将代码提交到LeetCode：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]

因为测试用例是一个非常长的字符串，导致我们的程序超出了时间限制，所以暴力穷举就解决不了这个问题了。

那能不能优化一下这段代码呢？

事实上，我们根本不需要从左到右遍历字符串穷举删除，可以定义两个指针，一个指向首，一个指向尾，然后让它们同时向中间移动，因为回文字符串的特点是从左到右读和从右到左读的结果是相同的，所以这两个指针经过的字符如果相同，则满足回文字符串的特点；如果不相同，则考虑删除某个字符之后是否满足回文字符串。

比如：

![在这里插入图片描述][42ca6ba7a91f4c7b999e4a210f02a9d0.png]

对于这样的一个字符串，我们在首尾设置两个指针：

![在这里插入图片描述][2e933eb5777e411da84badb533e414b1.png]

判断指针位置的字符是否相等，若相等，则指针i右移，指针j左移：

![在这里插入图片描述][f5d55a4879d6400e8805f4cec2a38bed.png]

继续判断指针位置的字符是否相等，因为相等，所以继续移动指针：

![在这里插入图片描述][bf4e30a58d5944e499f44075dd31d713.png]

此时指针i已经大于了指针j，遍历结束，由此得出该串是一个回文字符串。

再看一个需要删除字符的例子：

![在这里插入图片描述][dc2a7d1f163d4e85be7de49c1359e008.png]

指针i指向的字符为a，指针j指向的字符为c，两者不相同，这说明该串不是一个回文字符串，那么如何通过删除一个字符使其成为回文字符串呢？能够确定的是删除的字符一定是指针i和指针j指向的两个字符中的一个，因为是这两个字符不相同导致该串不是一个回文字符串，所以即使中间的字符再怎么样也改变不了这个事实，所以删除其中的一个字符，再去进行比较即可。

这里假设删除的字符是c：

![在这里插入图片描述][e95bbdd3d4c04a00a018f7e1774c1477.png]

现在两个指针指向的字符就相同了，那么移动指针：

![在这里插入图片描述][80ab9866a6eb4fb88f921f8e83310556.png]

指针重合，遍历结束。

由此得出代码如下：

public class Solution { 
    
        public static boolean validPalindrome(String s) { 
            // 声明首尾指针
            int i = 0;
            int j = s.length() - 1;
            // 开始遍历
            while (i < j) { 
                // 若两个指针指向的字符不相同，则考虑删除其中一个字符
                if (s.charAt(i) != s.charAt(j)) { 
                    // 若删除其中一个字符能够满足当前字符串为回文字符串，则返回true
                    return isPdStr(s, i + 1, j) || isPdStr(s, i, j - 1);
                }
                // 若两个指针指向的字符相同，则移动首尾指针
                ++i;
                --j;
            }
            return true;
        }
    
        /** * 判断是否为回文字符串 * * @param s * @return */
        public static boolean isPdStr(String s, int i, int j) { 
            for (int k = i; k <= i + (j - i) / 2; ++k) { 
                if (s.charAt(k) != s.charAt(j - k + i)) { 
                    return false;
                }
            }
            return true;
        }
    }

这里提取了一个判断给定字符串是否为回文字符串的方法，它仍然是通过双指针的方式进行判断，只不过需要考虑一些细节，比如：

![在这里插入图片描述][17bfb5bcae264a11ada12102056ee7c9.png]

对于这样的一个字符串，假设删除的是字符c，那么让j指针前移，此时i = 0，j = 2：

![在这里插入图片描述][0aae6d5b7c3a4036ae32eccf5349ae79.png]

将i和j传给isPdStr()方法进行判断，只需要进行字符串长度一半的次数比较即可，所以得出`i + (j - i) / 2`，首先`(j - i) / 2` 就能够计算出字符串长度的一半值，那为什么还要加i呢？  
这是因为字符串的左边很有可能已经删除了字符，所以那些字符是不能计算进去的。

同理，当判断两个指针的字符时，尾指针的计算方式也有所不同：`j - k + i`。

提交代码，测试通过：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 1]

[9729a291025b40f08355745cd57d7fa6.png]: /images/20220829/428e500baff44c45812584c52cafc1b0.png
[0f3650d17881487e909680cc6e91dd3a.png]: /images/20220829/137962283d9e43dba146b3b30ee23722.png
[0954bdcdb3ec44cc8bc24268f82bde1c.png]: /images/20220829/e545c69b4f3e4312acfb22885d613042.png
[a8dd30338a1640d9994198dd72bfe148.png]: /images/20220829/a624672c33ce447593459b92e328c7f1.png
[3f12d51057c9469fb30e7f78ece213d8.png]: /images/20220829/c18a6679ef4e453e93921b4456d130ca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]: /images/20220829/b99c650224b746a390a949067b937ba8.png
[42ca6ba7a91f4c7b999e4a210f02a9d0.png]: /images/20220829/a33d774270054dca8c966734ef493e60.png
[2e933eb5777e411da84badb533e414b1.png]: /images/20220829/0d30de6beb084d9697b9e5cfcf2fffd7.png
[f5d55a4879d6400e8805f4cec2a38bed.png]: /images/20220829/f4c4530a4390495487ccaf3eabf4477c.png
[bf4e30a58d5944e499f44075dd31d713.png]: /images/20220829/e65bd57df8644174a1f0e235223832e7.png
[dc2a7d1f163d4e85be7de49c1359e008.png]: /images/20220829/d50f49cc88374a63851cc5401556210c.png
[e95bbdd3d4c04a00a018f7e1774c1477.png]: /images/20220829/e2dc6129be9f4f03b09e19a128d7eb9f.png
[80ab9866a6eb4fb88f921f8e83310556.png]: /images/20220829/dc9b25be36654c9caf4e215507d9b497.png
[17bfb5bcae264a11ada12102056ee7c9.png]: /images/20220829/e62c556d6b6845978ad6025bdf7172ae.png
[0aae6d5b7c3a4036ae32eccf5349ae79.png]: /images/20220829/f6f3657722f84b979d34d116274d7772.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 1]: /images/20220829/e157f1b8ccf24f6c9f2237115d206c30.png