相关疑难解决方法(0)

这是来自Algorithms book(Vazirani)的问题(6.7 ch6),与发现最长回文的经典问题略有不同.我怎么解决这个问题 ？

如果从左到右或从右到左读取它是相同的,则子序列是回文.例如,序列

A,C,G,T,G,T,C,A,A,A,A,T,C,G

Run Code Online (Sandbox Code Playgroud)

有许多回文子序列,包括A,C,G,C,A和A,A,A,A (另一方面,子序列 A,C,T不是回文).设计一个算法,该算法采用一个序列x[1 ...n]并返回(最长的)最长的回文子序列.它的运行时间应该是O(n^2)

我似乎无法找到适当的练习方法.练习要求创建一个方法,如果字符串可以通过删除一个字符而成为回文,则返回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 …