确定给定字符串是否是 k 回文

Question

我正在尝试解决以下面试练习问题：

k-回文是一个在删除最多 k 个字符后转换为回文的字符串。

给定一个字符串 S 和一个整数 K，如果 S 是 k 回文，则打印“YES”；否则打印“NO”。

限制条件：

S最多 20,000 个字符。
0 <= k <= 30

测试用例示例：

Input - abxa 1 
Output - YES 

Input - abdxa 1 
Output - NO

我决定的方法是采用所有可能的长度s.length - k或更大的字符串组合，即“abc”和 k = 1 ->“ab”“bc”“ac”“abc”并检查它们是否是回文。到目前为止，我有以下代码，但似乎无法找出在一般情况下生成所有这些字符串组合的正确方法：

public static void isKPalindrome(String s, int k) {
  // Generate all string combinations and call isPalindrome on them,
  //   printing "YES" at first true 
}

private static boolean isPalindrome(String s) {
    char[] c = s.toCharArray()
    int slow = 0;
    int fast = 0;
    Stack<Character> stack = new Stack<>();
    while (fast < c.length) {
        stack.push(c[slow]);
        slow += 1;
        fast += 2;
    }
    if (c.length % 2 == 1) {
        stack.pop();
    }
    while (!stack.isEmpty()) {
        if (stack.pop() != c[slow++]) {
            return false;
        }
    }
    return true;
}

任何人都可以找到一种方法来实现这一点，或者也许展示更好的方法？

Answer 1

我认为有更好的方法

package se.wederbrand.stackoverflow;

public class KPalindrome {
    public static void main(String[] args) {
        KPalindrome kPalindrome = new KPalindrome();
        String s = args[0];
        int k = Integer.parseInt(args[1]);
        if (kPalindrome.testIt(s, k)) {
            System.out.println("YES");
        }
        else {
            System.out.println("NO");
        }
    }

    boolean testIt(String s, int k) {
        if (s.length() <= 1) {
            return true;
        }

        while (s.charAt(0) == s.charAt(s.length()-1)) {
            s = s.substring(1, s.length()-1);

            if (s.length() <= 1) {
                return true;
            }
        }

        if (k == 0) {
            return false;
        }

        // Try to remove the first or last character
        return testIt(s.substring(0, s.length() - 1), k - 1) || testIt(s.substring(1, s.length()), k - 1);
    }
}

由于 K 最大为 30，因此字符串可能很快就会失效，甚至无需检查字符串的中间部分。

我已经使用提供的两个测试用例以及一个 20k 字符长的字符串对此进行了测试，其中仅包含“ab”10k 次且 k = 30；

所有测试都很快并返回正确的结果。