LeetCode 680验证回文串II Java双指针460/466用例未过寻bug
问题排查结果
1. 存在的Bug点
- 边界判断错误:空字符串或长度为1的字符串本身就是合法回文,不需要删除任何字符即可满足要求,原代码直接返回
false,逻辑完全相反。 - 贪心选择逻辑错误:当左右指针字符不匹配时,同时存在「删除左指针字符」和「删除右指针字符」两种可行选择时,你的代码固定优先选择删左指针的路径,一旦这条路径后续不满足回文就直接返回失败,完全没有验证另一条路径的可行性,这是大部分测试用例失败的核心原因。
- 小问题:注释中
delect为拼写错误,应为delete。
2. 典型失败用例说明
比如官方测试用例aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga,第一次出现左右字符不匹配时,优先删除左指针的路径后续会出现不匹配,但删除右指针的路径可以完全匹配,你的代码会直接返回错误的false结果。
3. 修正方案
单独写一个验证子串是否为回文的辅助方法,当第一次遇到左右字符不匹配时,分别验证「删左后子串」和「删右后子串」是否是回文,只要其中一个是就返回true。
4. 修正后代码
class Solution { public boolean validPalindrome(String s) { if(s == null || s.length() <= 1) return true; int left = 0, right = s.length() - 1; while(left < right) { if(s.charAt(left) != s.charAt(right)) { // 两种删除情况只要有一种成立即可 return isPalindrome(s, left + 1, right) || isPalindrome(s, left, right - 1); } left++; right--; } return true; } // 辅助方法:验证s[left...right]是否为回文 private boolean isPalindrome(String s, int left, int right) { while(left < right) { if(s.charAt(left) != s.charAt(right)) { return false; } left++; right--; } return true; } }
内容的提问来源于stack exchange,提问作者user15939745
相关产品推荐
相关产品推荐

