题解 | #牛群密码 - 有效回文#

1. 题目考察的知识点

双指针，哈希表

2. 题目解答方法的文字分析

首先用哈希表收集不同的字符，看password的不同字符数是不是小于k。然后使用双指针。定义左右指针，初始化两个指针 low和 high分别指向字符串的第一个字符和最后一个字符。每次判断两个指针指向的字符是否相同，如果相同，则更新指针，low++，high--，然后判断更新后的指针范围内的子串是否是回文字符串。如果两个指针指向的字符不同，则两个字符中必须有一个被删除，此时我们就分成两种情况：即删除左指针对应的字符，留下子串 s[low+1:high]]，或者删除右指针对应的字符，留下子串 s[low:high−1]。当这两个子串中至少有一个是回文串时，就说明原始字符串删除一个字符之后就以成为回文串。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param password string字符串 
     * @param k int整型 
     * @return bool布尔型
     */
    public boolean isValidPalindrome (String password, int k) {
        HashSet<Character> set = new HashSet<>();
        for(int i=0;i<password.length();i++){
            if(!set.contains(password.charAt(i))){
                set.add(password.charAt(i));
            }
        }
        if(set.size()>k){
           return false;
        }
        int low = 0,high=password.length()-1;
        while(low<high){
            if(password.charAt(low)==password.charAt(high)){
                low++;
                high--;
            }else{
                return vaild(password,low,high-1)||vaild(password,low+1,high);
            }
        }
        return  true;
    }

    public boolean vaild(String s,int low ,int high){
        for(int i=low,j=high;i<j;i++,--j){
          if(s.charAt(i)!=s.charAt(j)){
            return false;
          }
        }
        return true;
    }
}