This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Source: LeetCode

Link: leetcode-cn.com/problems/lo…

Given a string s, find the longest substring in s.

Example 1:

Enter: s = “babad”

Output: “the bab”

Explanation: “ABA” is also a suitable answer to the question.

Example 2:

Input: s = “CBBD”

Output: “bb”

Example 3:

Input: s = “a”

Output: “a”

Example 4:

Input: s = “ac”

Output: “a”

Tip:

  • 1 <= s.length <= 1000
  • sConsists of only numbers and English letters (uppercase and/or lowercase)

title

First, make it clear that a palindrome string is a string that is read forward and read backward.

For example, the strings ABA and ABba are both palindromic strings because they are symmetric and, in reverse, identical to themselves. Conversely, the string abac is not a palindrome string.

Dynamic programming

It’s the same old dynamic three-step plan

  • If the string s is a palindrome string, then the new string must also be a palindrome string, such as “ABA” is a palindrome string, and “aabaa” is a palindrome string after “A”

  • State definition dp[I][j] indicates whether s[I…j] is a palindrome string

  • Dp [I][j] = DP [I + 1][J-1] &&s [I]== S [j]

class Solution {
    public String longestPalindrome(String s) {
        if (s.length() <= 1) {
            return s;
        }
        char[] chars = s.toCharArray();
        boolean[][] dp = new boolean[chars.length][chars.length];
        int start = 0;
        int end = 0;
        for (int j = 1; j < chars.length; j++) {
            for (int i = 0; i < j; i++) {
                if (chars[i] == chars[j] && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if(j - i > end - start) { start = i; end = j; }}}}return s.substring(start, end + 1); }}Copy the code

conclusion

Time: O(n2), because we’re filling up the DP array, which is n by n

Because of the new dp array, the space is O(n2), so it’s not an optimal solution, but it’s a good way to learn dynamic programming

I think the main difficulty in the three steps of dynamic programming is decomposition into sub-problems, but as long as the problem can be decomposed into sub-problems, the problem will be easily solved. Many problems are not so obvious to decompose sub-problems, I generally have to try, on the paper, to find the rule, not far from solving the problem.