Ray‘s Blog
0%

LeetCode-005,How to think step by step to dynamic planning

Posted on Edited on In Valine:

Q:

Given a string s, return the longest palindromic substring in s.

Input:

1
2
3
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

S:

If it is the first time that you are working on a similar topic, it is not really easy to think of using dynamic programming at once.

However, through step-by-step thinking and optimisation, the idea of using dynamic programming is actually a more natural one.

  1. First:

    Based on the requirements of the question, one of the simplest approaches would be to:
    1. Design a method judgeIsPalindrome , based on a double pointer, we can get an On to determine if String(i,j) is a palindrome
    2. enumerate all lengths k,judge all String(i,i+k-1) from largest to smallest, determine if it is a palindrome, if so, get the question requirement.

      This is a simple approach, but one problem is that it requires enumerating all k. The worst case requires enumerating N, and for each length, the worst case requires computing N times to get the result. So the overall complexity is high and cannot be passed. A more optimal approach needs to be found.

  2. Second

    1. One idea, based on the above, is not to enumerate every K, but to use the dichotomous search for the largest K instead, which would change the complexity to LogN. Try this idea yourself if you are interested.

      This idea above is likely to pass, but shows that it can still be optimized. We can note that another problem with the above approach is that each time we need to re-determine whether the new length of the substring is a palindrome or not, without making use of the previously computed result. Suppose that for a particular length $k_i$, we already know whether all substrings of length $k_i$ in String are palindromes. Then when we know whether String(i,i+$k_i$-1) is an echo, for String(i-1,i+$k_i$) in fact this result is also available in O1 time:

dp[i][j] = dp[i+1][j-1] ^ String[i] == String [j]

That is, String(i-1,i+$k_i$-1) can only be a palindrome if String(i,i+$k_i$-1) is a palindrome and String[i] == String [j].

The following DP code can be written:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2) {
        return s;
    }
    boolean[][] dp = new boolean[len][len];
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }
    int maxLen = 1;
    int start = 0;
    for (int j = 1; j < len; j++) {
        for (int i = j - 1; i >= 0; i--) {
            if (s.charAt(i) == s.charAt(j)) {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            } else {
                dp[i][j] = false;
            }

            if (dp[i][j]) {
                int curLen = j - i + 1;
                if (curLen > maxLen) {
                    maxLen = curLen;
                    start = i;
                }
            }
        }
    }
    return s.substring(start, start + maxLen);
}