网站排名推广工具,免费小程序制作平台,网站设计宁波,移动端企业网站19.验证回文串II 方法#xff1a;双指针
首先考虑如果不允许删除字符#xff0c;如何判断一个字符串是否是回文串。常见的做法是使用双指针。定义左右指针#xff0c;初始时分别指向字符串的第一个字符和最后一个字符#xff0c;每次判断左右指针指向的字符是否相同#…19.验证回文串II 方法双指针
首先考虑如果不允许删除字符如何判断一个字符串是否是回文串。常见的做法是使用双指针。定义左右指针初始时分别指向字符串的第一个字符和最后一个字符每次判断左右指针指向的字符是否相同如果不相同则不是回文串如果相同则将左右指针都往中间移动一位直到左右指针相遇则字符串是回文串
在允许最多删除一个字符的情况下同样可以使用双指针通过贪心实现。初始化两个指针 low和 high 分别指向字符串的第一个字符和最后一个字符。每次判断两个指针指向的字符是否相同如果相同则更新指针将 low 加 1high 减 1然后判断更新后的指针范围内的子串是否是回文字符串。如果两个指针指向的字符不同则两个字符中必须有一个被删除此时我们就分成两种情况即删除左指针对应的字符留下子串 s[low1:high]或者删除右指针对应的字符留下子串 s[low:high−1]。当这两个子串中至少有一个是回文串时就说明原始字符串删除一个字符之后就以成为回文串。
class Solution {public boolean validPalindrome(String s) {int low 0, high s.length() - 1;while(low high){if(s.charAt(low) s.charAt(high)){low;high--;}else{return validPalind(s,low,high - 1) || validPalind(s,low1,high);}}return true;}public boolean validPalind(String s,int low,int high){for(int i low,j high;i j; i,j--){char c1 s.charAt(i),c2 s.charAt(j);if(c1 ! c2){return false;}}return true;}
}
