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

Question

我似乎无法找到适当的练习方法.练习要求创建一个方法,如果字符串可以通过删除一个字符而成为回文,则返回true.我有一个解决方案,但无法测试大型(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).

回文由a组成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

我们可以很容易地看到,它包含原始的回文定义,但另外还允许引入一个额外的char 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;
}

解释/或至少试图解释一下:
这段代码:

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)确切地说).建立更快的解决方案是不可能的 - 至少在我们得到量子计算机之前;)