确定给定的字符串是否为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或更长的所有可能的字符串组合拿出来，例如当s为"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;
}

有没有人能想出一种实现这个的方法，或者展示一种更好的方法？

- Brandon

---

Apache Commons，StringUtils.reverse。它应该是："abxa".equals(StringUtils.reverse("abxa"))。 - Jorge Campos

你应该在问题中详细描述你的问题，而不是让别人从你的评论中推断，因为标题可能会误导。 - Slater Victoroff

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，因��很可能字符串会很快无效，甚至不必检查字符串的中间部分。

我已经使用提供的两个测试用例以及一个包含10k次“ab”的20k字符长字符串和k = 30进行了测试;

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

- Andreas Wederbrand

---

非常感谢！这很棒，比我的好，子字符串可能比字符数组更好的想法。 - Brandon

递归的最大深度应为K，在这种情况下达到了这个限制。 - Luka Rahne

有时候像人类一样思考会很有帮助。这就是我在纸上解决问题的方式。祝你面试顺利。 - Andreas Wederbrand

@AndreasWederbrand 方法testIt被调用的次数将是(20000^2)*30，因为有20000^2个不同的可能子字符串，每个子字符串都有30个不同的k值。我认为它不会运行得很快。你的算法在最坏情况下需要多长时间？ - Nikunj Banka

这是指数级时间，最好不要标记为正确答案。最好使用动态规划方法。 - rexar5

Answer 2

这可以使用编辑距离动态规划算法来解决。编辑距离DP算法用于查找将源字符串转换为目标字符串所需的最小操作次数。操作可以是添加或删除字符。

通过检查将输入字符串转换为其反转所需的最小操作，可以使用编辑距离算法解决K-回文问题。

让editDistance（source，destination）成为函数，该函数接受源字符串和目标字符串，并返回将源字符串转换为目标字符串所需的最小操作次数。

如果editDistance（S，reverse（S））<= 2 * K，则字符串S是K-回文。这是因为我们可以通过最多删除K个字母，然后在不同的位置插入相同的K个字母来将给定的字符串S转换为其反转。

这将通过一个例子更清晰。

假设S = madtam且K = 1。

要将S转换为其反转（即matdam），首先我们必须删除S中索引3处（基于0的索引）的字符“t”。

现在的中间字符串是“madam”。然后我们需要在中间字符串的索引2处插入字符“t”，以得到字符串s的反向字符串“matdam”。如果仔细观察，你会知道中间字符串“madam”是通过删除k=1个字符得到的回文字符串。

- Vishnu

---

嘿，我认为对于K回文，正确的条件应该是editDistance（S，reverse（S））<= 2*K，因为它说最多k个字符。请在我的答案中检查推理。 - Nivetha

谢谢！已更新答案 :-) - Vishnu

Answer 3

我找到了一种方法来计算最长字符串长度，使得在删除字符>= k之后，我们仍然可以得到一个回文字符串。我在这里使用了动态规划。我所考虑的回文字符串不必是连续的。例如，abscba的最长回文长度为4。

现在可以进一步使用它，每当k>=(len-最长回文长度)时，结果为真，否则为假。

 public static int longestPalindrome(String s){
        int len = s.length();
        int[][] cal = new int[len][len];
        for(int i=0;i<len;i++){
            cal[i][i] = 1; //considering strings of length = 1
        }
        for(int i=0;i<len-1;i++){
            //considering strings of length = 2
            if (s.charAt(i) == s.charAt(i+1)){
                cal[i][i+1] = 2;
            }else{
                cal[i][i+1] = 0;
            }
        }

        for(int p = len-1; p>=0; p--){
            for(int q=p+2; q<len; q++){
                if (s.charAt(p)==s.charAt(q)){
                    cal[p][q] = 2 + cal[p+1][q-1];
                }else{
                    cal[p][q] = max(cal[p+1][q], cal[p][q-1]);
                }
            }
        }
        return cal[0][len-1];
    }

- Shilpa

Answer 4

这是一个常见的面试问题，我有点惊讶没有人提到动态规划。这个问题展现了最优子结构（如果一个字符串是k-回文，一些子串也是k-回文），和重叠子问题（解决方案需要比较相同的子串多次）。

这是编辑距离问题的特例，我们检查字符串s是否可以通过仅删除两个字符串中的字符之一或两者都删除来转换为字符串p。

让字符串为s及其反向rev。 让dp[i][j]表示将s的前i个字符转换为rev的前j个字符所需的删除数。由于必须在两个字符串中执行删除操作，因此如果dp[n][n] <= 2 * k，则该字符串是k-回文。

基本情况：当其中一个字符串为空时，需要删除另一个字符串中的所有字符才能使它们相等。

时间复杂度：O(n^2)。

Scala代码:

def kPalindrome(s: String, k: Int): Boolean = {
    val rev = s.reverse
    val n = s.length
    val dp = Array.ofDim[Int](n + 1, n + 1)

    for (i <- 0 to n; j <- 0 to n) {
      dp(i)(j) = if (i == 0 || j == 0) i + j
      else if (s(i - 1) == rev(j - 1)) dp(i - 1)(j - 1)
      else 1 + math.min(dp(i - 1)(j), dp(i)(j - 1))
    }
    dp(n)(n) <= 2 * k
}

由于我们正在进行自底向上的DP，如果在任何时候i == j && dp [i] [j]> 2 * k ，则优化是返回false，因为所有后续的i == j必须更大。

- Abhijit Sarkar

---

我也很惊讶没有人提到动态规划。如果你们在这里使用任何其他方法，由于这些解决方案具有可怕的时间复杂度（指数级），你将无法获得一个offer/另一个面试机会。@Abhijit，点个赞。如果我是OP，你就会被标记为正确答案。 - rexar5

Answer 5

这个问题可以使用著名的最长公共子序列(LCS)方法来解决。当LCS应用于字符串和给定字符串的反转时，它会给出字符串中存在的最长回文子序列。

假设给定长度为string_length的字符串的最长回文子序列长度为palin_length。那么(string_length - palin_length)就是将字符串转换为回文所需删除的字符数。因此，如果(string_length - palin_length) <= k，则给定的字符串是k-回文。

让我举几个例子：

初始字符串：madtam（string_length = 6）

最长回文子序列：madam（palin_length = 5）

非贡献字符数：1（string_length - palin_length）

因此，这个字符串是k-回文，其中k>=1。这是因为你需要最多删除k个字符（k个或更少）。

以下是代码片段：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 10000

int table[MAX+1][MAX+1];
int longest_common_subsequence(char *first_string, char *second_string){
    int first_string_length = strlen(first_string), second_string_length = strlen(second_string);
    int i, j;
    memset( table, 0, sizeof(table));
    for( i=1; i<=first_string_length; i++ ){
        for( j=1; j<=second_string_length; j++){
            if( first_string[i-1] == second_string[j-1] )
                table[i][j] = table[i-1][j-1] + 1;
            else
                table[i][j] = max(table[i-1][j], table[i][j-1]);
        }
    }
    return table[first_string_length][second_string_length];
}

char first_string[MAX], second_string[MAX];

int main(){
    scanf("%s", first_string);
    strcpy(second_string, first_string);
    reverse(second_string, second_string+strlen(second_string));
    int max_palindromic_length = longest_common_subsequence(first_string, second_string);
    int non_contributing_chars = strlen(first_string) - max_palindromic_length;
    if( k >= non_contributing_chars)
        printf("K palindromic!\n");
    else 
        printf("Not K palindromic!\n");
    return 0;
}

- Nivetha

Answer 6

我设计了一个完全基于递归的解决方案 -

public static boolean isKPalindrome(String str, int k) {
            if(str.length() < 2) {
                return true;
            }

            if(str.charAt(0) == str.charAt(str.length()-1)) {
                return isKPalindrome(str.substring(1, str.length()-1), k);
            } else{
                if(k == 0) {
                    return false;
                } else {
                    if(isKPalindrome(str.substring(0, str.length() - 1), k-1)) {                        
                        return true;
                    } else{
                        return isKPalindrome(str.substring(1, str.length()), k-1);
                    }                   
                }
            }
        }

上述实现中没有while循环，与被接受的答案不同。 希望能对寻找此内容的人有所帮助。

- Shadab Ansari

Answer 7

   public static boolean failK(String s, int l, int r, int k) {

        if (k < 0)
            return false;

        if (l > r)
            return true;

        if (s.charAt(l) != s.charAt(r)) {
            return failK(s, l + 1, r, k - 1) || failK(s, l, r - 1, k - 1);
        } else {
            return failK(s, l + 1, r - 1, k);
        }
    }

- Ninja Dude

Answer 8

感谢Andreas，那个算法非常好用。这是我的实现方式，供任何有兴趣的人参考。稍微有些不同，但基本上是相同的逻辑：

public static boolean kPalindrome(String s, int k) {
    if (s.length() <= 1) {
        return true;
    }
    char[] c = s.toCharArray();
    if (c[0] != c[c.length - 1]) {
        if (k <= 0) {
            return false;
        } else {
            char[] minusFirst = new char[c.length - 1];
            System.arraycopy(c, 1, minusFirst, 0, c.length - 1);
            char[] minusLast = new char[c.length - 1];
            System.arraycopy(c, 0, minusLast, 0, c.length - 1);
            return kPalindrome(String.valueOf(minusFirst), k - 1)
                   || kPalindrome(String.valueOf(minusLast), k - 1);
        }
    } else {
        char[] minusFirstLast = new char[c.length - 2];
        System.arraycopy(c, 1, minusFirstLast, 0, c.length - 2);
        return kPalindrome(String.valueOf(minusFirstLast), k);
    }
}

- Brandon

---

如果 k == 0，你可以直接循环遍历数组，检查它是否为回文 - 不需要进一步递归。此外，我不建议在每个递归步骤中创建一个 char[]（或 String） - 你可以只在原始字符串中跟踪当前左右索引。 - Bernhard Barker