返回最长回文子串[Java]

Question

这是我使用带有记忆功能的动态编程编写的最长回文解决方案。 它通过了几个测试用例 (46/142)，但在 Leetcode 上解决方案并不是 100%。对于很长的输入，超出了时间限制 (TLE)。如何让它也适用于长输入？

public String longestPalindrome(String s) {
    Map<List<Integer>, String> memo = new HashMap<>();
    return longest(s, 0, s.length()-1, memo);
}

public static String getMaxString(String s1, String s2) {
    return (s1.length() > s2.length() ? s1 : s2);
}

public String longest(String s, int i, int j, Map<List<Integer>, String> memo) {
    // Invalid indices.
    if (i > j) {
        return "";
    }
    
    List<Integer> keyPair = List.of(i, j);
    if (i == j) {
        return s.substring(i, j+1);
    }

    // Return palindrome if already evaluated.
    if(memo.containsKey(keyPair)) {
        return memo.get(keyPair);
    }
    
    // Check if the inner string is also a palindrome and update max accordingly.
    String max = longest(s, i+1, j-1, memo);
    if ((max.length() == (j-1) - (i+1) + 1) &&
        (s.charAt(i) == s.charAt(j)))
    {
        max = s.substring(i,j+1);
    }

    // Get max of all possible palindromes within [i,j].
    max = getMaxString(max, getMaxString(longest(s, i+1, j, memo),
                                         longest(s, i, j-1, memo)));

    memo.put(keyPair, max);
    return memo.get(keyPair);
}

我已经看到了解决这个问题的各种其他算法，但是，我特别寻找的是了解如何使我的解决方案适用于所有输入（或）解决方案中的差距。

Answer 1

首先，您的解决方案是

O(N^3)

：您有

O(N^2)

状态（与子字符串对应的可能的索引对），并且在每个递归调用中调用

substring

，即

O(N)

。

不需要从递归

longest

方法返回实际字符串，只需返回一对整数来表示子字符串。这种表示允许恒定时间操作；最后只需要调用

substring

即可得到结果。

此外，虽然

HashMap

平均提供恒定时间操作，但它仍然可能相当慢。在这种情况下，您已经知道可能的键值（索引都在

0

和

s.length() - 1

之间），因此使用二维数组来存储记忆结果会更有效。

public String longestPalindrome(String s) {
    var memo = new int[s.length()][s.length()][];
    var ret = longest(s, 0, s.length()-1, memo);
    return s.substring(ret[0], ret[1]);
}

public static int[] getMaxString(int[] s1, int[] s2) {
    return s1[1] - s1[0] > s2[1] - s2[0] ? s1 : s2;
}

public int[] longest(String s, int i, int j, int[][][] memo) {
    if (i > j) {
        return new int[2];
    }
    if (i == j) {
        return new int[]{i, j+1};
    }
    if (memo[i][j] != null) return memo[i][j];
    var max = longest(s, i+1, j-1, memo);
    if ((max[1] - max[0] == (j-1) - (i+1) + 1) &&
        (s.charAt(i) == s.charAt(j))) {
        max = new int[]{i, j+1};
    }
    max = getMaxString(max, getMaxString(longest(s, i+1, j, memo),
                                         longest(s, i, j-1, memo)));

    return memo[i][j] = max;
}