删除一个字符后检查字符串是否为回文。我的工作解决方案太慢

Question

我似乎找不到合适的练习题。该练习要求创建一个方法，如果一个字符串可以通过删除一个字符成为回文，则该方法 returns 为真。我有一个可行的解决方案，但无法通过大（100,000 个字符）字符串的测试，因为它超过了 1 秒的时间限制。有人能指出我正确的方向吗？

我意识到我的方法是蛮力，我相信有更好的方法来解决它。我假设我的问题在于迭代。

public class Main {

    public static boolean makePalindrome(String mjono) {

        StringBuilder sb = new StringBuilder(mjono);


        for (int i = 0; i < mjono.length(); i++) {
            sb.deleteCharAt(i);

            if(isPalindrome(sb.toString())){
                return true;
            } else {
                sb.insert(i, mjono.charAt(i));
            }
        }
        return false;
    }

    private static boolean isPalindrome(String string) {
        return string.equals(new StringBuilder(string).reverse().toString());
    }

    public static void main(String[] args) {
        System.out.println(makePalindrome("ABCBXA"));
        System.out.println(makePalindrome("ABCBAX"));
        System.out.println(makePalindrome("ABCXBA"));
        System.out.println(makePalindrome("ABCDE"));
        System.out.println(makePalindrome("BAAAAC"));
    }
}

这些是它失败的测试：

@Test(timeout=1000)
public void suuri2() {
    int n = 100000;
    char[] t = new char[n];
    for (int i = 0; i < n; i++) t[i] = 'A';
    t[12345] = 'B';
    testaaSuuri(new String(t), true);
}

@Test(timeout=1000)
public void suuri3() {
    int n = 100000;
    char[] t = new char[n];
    for (int i = 0; i < n; i++) t[i] = 'A';
    t[12345] = 'B';
    t[54321] = 'C';
    testaaSuuri(new String(t), false);
}

提前致谢。

Answer 1

嗯，在 O(n ^ 2) 中当然有天真的解决方案运行通过尝试每种可能性来删除一个字符。

但我们当然可以做得更好：
我们可以递归地定义回文：

palindrome = x.palindrome.x | x | x.x , where x is an arbitrary token

那么这对我们有什么帮助呢？非常简单：我们可以推导出一个规则，允许检查 O(n) 中的字符串是否为回文。

一个回文包含一个 char c，后跟一个必须为空或回文的字符串，然后是另一个 c，如果它的长度超过 1 个字符。如果它的长度为 1，它会自动回文。

因此，最后一个字符必须等于第一个字符，第二个字符必须等于倒数第二个字符，依此类推。所以基本上：

boolean isPalindrome(String s){
    for(int i = 0 ; i < s.length() / 2 ; i++)
        if(s.charAt(i) != s.charAt(s.length() - i - 1))
            return false;

    return true;
}

我们必须稍微改变一下这个规则，因为一旦我们可以删除一个字符。这引入了将整个问题分成两部分，正如我们可以从定义中看到的那样：

palindrome_1 = s.x.palindrome.reverse(s) | s.palindrome.x.reverse(s) | palindrome

我们可以很容易地看到，这包含原始回文定义，但另外允许引入一个额外的字符 x.

static boolean isPalindrome_1(String s){
    for(int i = 0 ; i < s.length() / 2 ; i++)
        if(s.charAt(i) != s.charAt(s.length() - i - 1))
            return isPalindrome(s , i + 1 , s.length() - i - 1) ||
                    isPalindrome(s , i , s.length() - i - 2);

     return true;
}

static boolean isPalindrome(String s , int lower , int upper){
    while(lower < upper){
        if(s.charAt(lower) != s.charAt(upper))
            return false;

        lower++;
        upper--;
    }

    return true;
}

explanation/or 至少尝试解释一下：
这段代码：

if(s.charAt(i) != s.charAt(s.length() - i - 1))
    return isPalindrome(s , i + 1 , s.length() - i - 1) ||
        isPalindrome(s , i , s.length() - i - 2);

是必需的，如果 palindrome 的定义不适用于我们的输入字符串。在那种情况下，我们必须检查两种可能性，代码是如何构建的：

s.x.palindrome.reverse(s)
s.palindrome.x.reverse(s)

如果 palindrome 的定义不适用，我们已经到了一个点，我们是否必须省略剩余字符串开头的字符 (x.palindrome) 或剩余字符串的末尾 (palindrome.x) 并查看其余部分是否与回文的定义匹配。这是通过使用两个不同的子字符串调用 isPalindrome(...) 来完成的，这两个子字符串在剩余字符串的开头或结尾被一个字符剪切。

此代码如何工作的几个示例：

A B C D E F E D C B A
|                   | portion that runs inside isPalindrome_1

A B D E F E D C B A
| |             | |  portion that can be checked inside isPalindrome_1
    |       |        isPalindrome(s , i , s.length() - i - 2)
      |       |      isPalindrome(s , i + 1 , s.length() - i - 1)

正如我们在第二个示例中看到的那样，代码搜索了第一对不相等的字符。此时，我们有两个子字符串需要进一步搜索，每个子字符串在字符串的开头或结尾省略一个字符。

效率：
此代码就地运行 - 从未制作任何输入字符串的副本。运行时为 O(n)（准确地说是 O(2 * n)）。构建一个更快的解决方案是不可能的——至少在我们得到量子计算机之前是这样 ;)

Answer 2

只需要对比一下上半场和下半场。也不要浪费时间反转整个字符串。

private boolean isPalindrome(String string) {
    char[] values = string.toCharArray();

    for (int i = 0; i < values.length / 2; i++) {
       if (values[i] != values[values.length - 1 - i])
           return false;
    }

    return true;
}

Answer 3

提示1：由于这是一个练习，所以发布解决方案是不合适的。（有损自己做功法的学习体验。）

提示2：以下操作都是O(N)对于一个N个字符串或StringBuilder：

从 StringBuilder 添加或删除字符
从现有的 StringBuilder 创建新的 StringBuilder
反转 StringBuilder
从 StringBuilder 创建字符串 (toString())
比较两个相等或 "almost equal" 字符串对象。

(在大多数情况下，您复制或比较 N 个字符。对于插入和删除，假设缓冲区不需要增长，您平均复制 0.5 N 个字符，但这仍然是 O(N)。对于equals ...这很复杂，但最坏的情况显然是O(N)。）

因此，快速大字符串回文测试器需要避免这些操作。

提示 3：您可以将字符串视为字符数组，方法是将其转换为 char[] 或使用 charAt(...).

提示 4：您不必从字符串中物理删除字符。你可以让你的算法假装它不存在。

Answer 4

我们可以使用LCS（最长公共子序列）来解决这个问题。 LCS 告诉我们两个字符串中最长子序列的长度。

boolean isPalindromAfterRemovingOneChar(String s) {
    int lengthOfLCS = lcs(s, s.reverse(), s.length());
    return (s.length()- lengthOfLCS) == 1;
}

删除一个字符后检查字符串是否为回文。我的工作解决方案太慢

Check if string is a palindrome after removing one character. My working solution is too slow

java

string

algorithm

palindrome