Topic describes

Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000. Example 1: Input: "babad" Output: "bab" Note: "ABA" is also a valid answer. Example 2: Input: "CBBD" Output: "bb"Copy the code

Idea 1: Center diffusion

First let’s confirm what is a palindrome string. Aba is a palindrome string and AA is a palindrome string. That is to say, palindromes are divided into two cases, where an odd length starts with a single character in the middle and spreads out. Even characters need to start with the middle two characters. There are therefore two modes of diffusion to consider.

The code is as follows:

// From l to left and from r to right, String palindrome(string s, int l, int r) {while(l >= 0 &&r < s.size() &&s [l] == s[r]) {l--; r++; } return s.substr(l+1, r-l-1); } string longestPalindrome(string s) { if(s.size() == 0) { return ""; } string ans = s.substr(0, 1); for(int i = 0; i < s.size()-1; String same = palindrome(s, I, I); string same = palindrome(s, I, I); NotSame = palindrome(s, I, I +1); notSame = palindrome(s, I, I +1); ans = ans.size() < same.size() ? same : ans; ans = ans.size() < notSame.size() ? notSame : ans; } return ans; }Copy the code

Time is O (n*n), space is O (1).

Idea 2 Dynamic planning

The array dp[I][j] indicates whether the substring of the [I,j] interval in the string s is a palindrome. What we do know is this:

1. if(i == j) dp[i][j] = true
2. if(i < j) dp[i][j] = false
Copy the code

How to solve for other values according to dp[I][j]?

If s [I]! P [I][j]=false

In the case of s[I]==s[j], if dp[I +1][j-1]=true, then dp[I][j]=true, then we can obtain the state transition equation:

dp[i][j] = dp[i+1][j-1] && s[i]==s[j]
Copy the code

According to the figure above, at this point we can already determine the value of dp[I][j] because the prerequisites are already there. However, we also need to take into account that in the case of dp[I][I +1], namely j-i+1=2, we only need to judge whether S [I] and S [j] are equal. For example, when solving dp[0][1], dp[1][0]=false has lost reference value. The code is as follows:

string longestPalindrome(string s) { size_t length = s.size(); int dp[length][length]; int maxLen = 1; int start = 0; for(int i = 0; i < length; i++) { dp[i][i] = true; } for(int j = 1; j < length; j++) { for(int i = 0; i < j; i++) { if(s[i] ! = s[j]) { dp[i][j] = false; }else { if(j - i < 2) { dp[i][j] = true; }else { dp[i][j] = dp[i+1][j-1]; } if(dp[i][j] && j-i+1 > maxLen) { start = i; maxLen = j-i+1; } } } } return s.substr(start, maxLen); }Copy the code

Time is O (n*n), space is O (n*n).