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

import java.util.*;


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

    public boolean isPalindrome(String str) {
        StringBuffer stringBuffer = new StringBuffer();
        stringBuffer.append(str);
        return stringBuffer.reverse().toString().equals(str);
    }
}

本题考察的知识点是字符串的回文判断和字符的频率统计，所用编程语言是java。

关于统计字符串中有多少个不同的字符，可以使用一个HashSet来进行统计，将字符串的每个字符加入HashSet中然后看set的大小有多少就知道字符串有多少个不同的字符。然后判断该字符串是否能够删除一个字符构成回文串，我们可以使用两个指针一个指针指向字符串的首端，一个指针指向字符串的末端，然后判断两个指针指向的字符是否相等，如果相等两个指针则继续开始移动，否则删除其中一个字符判断剩余的字符能否构成回文串