java - 确定给定字符串是否为 k 回文

Question

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

A k-palindrome is a string which transforms into a palindrome on removing at most k characters.

Given a string S, and an integer K, print "YES" if S is a k-palindrome; otherwise print "NO".

Constraints:

S has at most 20,000 characters.
0 <= k <= 30

Sample Test Cases:

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；

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