This is the 8th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021
The title
Given a string s, find the longest substring in s.
Example 1:
Input: s = “babad” Output: “bab” Explanation: “ABA” is also the answer to the question. Example 2:
Input: s = “CBBD” Output: “bb” Example 3:
Input: s = “a” Output: “a” Example 4:
Input: s = “AC”
Tip:
1 <= S. length <= 1000 s Consists of only digits and letters (uppercase and/or lowercase)
Train of thought
So in order to do this problem you need to understand what are palindromes and substrings
- Palindrome: The order from left to right is the same as from right to left, with the property of axial symmetry
- Substring: A substring is a contiguous part of the original string
Since it is axially symmetric, the first thing that comes to mind is that the string on the axis expands to the two sides, so there are two more situations
- Odd symmetry, such as “bab,” requires comparing the left and right characters to see if they are equal
- Even symmetry, such as the “baab” form, requires comparisons between current and left and right
Code implementation
public static String longestPalindrome(String s) {
// There is no need to save the substring, just remember the starting position and length
int maxStart = 0, maxLen = 0;
for (int i = 0; i < s.length(); i++) {
int left = i - 1;
int right = i + 1;
int currLen = 1;
// Even symmetry, the current character is equal to the left character, the length of the substring +1
while (left >= 0 && s.charAt(left) == s.charAt(i)) {
currLen++;
left--;
}
// Even is symmetric, the current character is equal to the right character, and the length of the substring is +1
while (right < s.length() && s.charAt(right) == s.charAt(i)) {
currLen++;
right++;
}
// Odd symmetry, the left and right sides of the current character are equal, and the length of the substring is +2
while (left >= 0 && right < s.length() && s.charAt(right) == s.charAt(left)) {
currLen = currLen + 2;
left--;
right++;
}
if(currLen > maxLen) { maxLen = currLen; maxStart = left; }}return s.substring(maxStart + 1, maxStart + maxLen + 1);
}
Copy the code
Execution time: 44 ms, beating 60.33% of all Java commits
Memory consumption: 38.1 MB, beating 97.80% of all Java commits
To optimize the
In fact, the above solution does a lot of double calculation, dynamic programming is to reduce the problem of double calculation. Dynamic programming sounds fancy. In fact, it is space for time, the results of the calculation of temporary storage, to avoid double calculation.
Palindromes have the nature of state transition: after a palindrome is removed, the remaining part is still a palindrome. On the other hand, if the first and last characters of a string are not equal, the string must not be a palindrome. The method of dynamic programming follows from this property.
Step 1: define the state dp[I][j] indicates whether the substring S [I..j] is a returnee substring, where the substring S [I..j] is defined as the left closed and right closed interval, that is, s[I] and S [j] can be obtained.
Step 2: According to whether the beginning and end characters are equal, the state transition equation deduces whether the string is palindrome or not depending on whether the end is palindrome or not
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
Step 3: Initialize
Initialize a Boolean array with a flag bit to indicate whether it is a palindrome
public String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
int maxStart = 0;
int maxEnd = 0;
int maxLen = 1;
boolean[][] dp = new boolean[s.length()][s.length()];
for (int r = 1; r < s.length(); r++) {
for (int l = 0; l < r; l++) {
//r +1 <= 2; r +1 <= 2; r +1 <= 2
if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
dp[l][r] = true;
if (r - l + 1 > maxLen) {
maxLen = r - l + 1; maxStart = l; maxEnd = r; }}}}return s.substring(maxStart, maxEnd + 1);
}
Copy the code
summary
This problem began to involve common dynamic planning ideas, and then encountered several dynamic planning problems, will try to summarize the template of dynamic planning, so that after encountering again will not be confused, at least some ideas.