Article directory
- 1. 【LeetCode】647. Palindrome substring
-
- 1.1 Idea explanation
-
- 1.1.1 Method selection
- 1.1.2 Creation of dp table
- 1.1.3 State transition equation
- 1.1.4 Order of filling out the form
- 1.2 Overall code
- 2. 【LeetCode】5. The longest palindrome string
-
- 2.1 Idea explanation
- 2.2 Code implementation
- 3.【LeetCode】094. Split Palindrome II
-
- 3.1 Problem-solving ideas
-
- 3.1.1 Create dp table
- 3.1.2 State transition equation
- 3.1.3 Find out whether all substrings are palindrome strings in advance
- 3.2 Overall code
- 4.【LeetCode】516. Longest Palindromic Subsequence
-
- 4.1 Idea explanation
-
- 4.1.1 Create dp table
- 4.1.2 State transition equation
- 4.1.3 There is no need to consider the boundary problem
- 4.2 Overall code
- 5. 【LeetCode】1312. Minimum number of insertions to make a string a palindrome
-
- 5.1 Idea explanation
-
- 5.1.1 Create dp table
- 5.1.2 State transition equation
- 5.1.3 There is no need to consider the boundary problem
- 5.2 Overall code
1. 【LeetCode】647. Palindrome substring
topic link
1.1 Idea explanation
1.1.1 Method selection
We use the dynamic programming solution to this question, not how good the dynamic programming solution is for this question, it is not the optimal solution. However, the dynamic programming idea of this question is very useful. We can turn some hard questions into easy questions by using the dynamic programming idea of this question.
That is to say, the dynamic programming idea of this question actually plays a role of attracting jade.
1.1.2 Creation of dp table
How to express all substrings? You can use i to represent the starting position of a certain substring, use j to represent the end position of a certain substring, and use violent enumeration to find out whether all substrings are palindromic substrings within the time complexity of N^2.
So, we use a two-dimensional dp[i][j] table to indicate whether a substring starting at position i and ending at position j is a palindromic substring. If it is a palindrome substring then dp[i][j] is true, otherwise it is false. (We artificially stipulate that i <= j)
1.1.3 State transition equation
We need to know whether dp[i][j] is a palindrome substring, first we need to judge whether s[i] is equal to s[j].
If s[i] != s[j], no matter what the sequence of elements between i and j is, the substring starting at position i and ending at position j< strong>Must not be a palindrome substring.
If s[i] == s[j], then the positions of i and j need to be judged.
- If i == j, it means that the current initial position and the end position are at the same position, that is to say, the substring has only one element, at this time it is a palindromic substring according to the meaning of the question ;
- If i + 1 == j, then the positions of i and j are adjacent. At this time, there is no element between them, and the elements at their positions are the same. Then it must be a palindrome substring ;
- If i + 1 < j, it means that there are other elements between position i and position j. At this time, it is only necessary to judge whether dp[i + 1][j-1] is true or false. Yes.
1.1.4 Form filling order
Since we need to use dp[i + 1][j-1] when we seek dp[i][j], and the loop of i is the outer loop, so let i loop from large to small.
1.2 Overall Code
class Solution {<!-- -->
public:
int countSubstrings(string s) {<!-- -->
int n = s. size();
// Create a two-dimensional dp table, the initial value of each position in the dp table is false
vector<vector<bool>> dp(n, vector<bool>(n));
int ret = 0; // used to save the dp position of how many true bits, that is, how many palindrome substrings
// When looping, i loops from large to small
for (int i = n - 1; i >= 0; --i)
{<!-- -->
// The loop order of j doesn't really matter, as long as the interval of the loop is in [i, n)
for (int j = i; j < n; + + j)
{<!-- -->
// Find dp[i][j] according to the state transition equation
if (s[i] == s[j])
dp[i][j] = i + 1 < j ? dp[i + 1][j-1] : true;
// If dp[i][j] is true, add ret
if (dp[i][j]) + + ret;
}
}
return ret;
}
};
2. 【LeetCode】5. The longest palindrome
topic link
2.1 Idea explanation
It is not much different from the idea of finding a palindrome substring
It means that after finding each palindrome substring, instead of counting how many palindrome substrings there are, it just picks out the longest palindrome substring and returns it after the loop ends.
The code has only changed a little bit.
2.2 Code Implementation
class Solution {<!-- -->
public:
string longestPalindrome(string s) {<!-- -->
int n = s. size();
vector<vector<bool>> dp(n, vector<bool>(n));
int start = 0; // the starting position of the longest palindrome substring
int len = 0; // length of the longest palindrome substring
for (int i = n - 1; i >= 0; --i)
{<!-- -->
for (int j = i; j < n; + + j)
{<!-- -->
if (s[i] == s[j])
dp[i][j] = i + 1 < j ? dp[i + 1][j-1] : true;
// If the position is a palindrome substring, then determine whether the length is greater than the previous longest length
// If greater than, update the starting position and longest length
if (dp[i][j] == true & amp; & amp; j - i + 1 > len)
{<!-- -->
len = j - i + 1;
start = i;
}
}
}
// Return the longest palindrome substring according to the starting position and length
return s.substr(start, len);
}
};
3.【LeetCode】094. Split Palindrome II
3.1 Problem-solving ideas
3.1.1 Create dp table
We use dynamic programming to solve this problem. First, create a dp table whose size is the length of the string. dp[i] indicates how many minimum divisions of the string of s[0, i] can be fully divided into palindrome strings.
3.1.2 State transition equation
To find the state transition equation, we have to consider two cases. s[0, i] is a palindrome and not a palindrome.
Note, here it is assumed that we already know which string is a palindrome, and how to know it will be discussed later.
- If s[0, i] is a palindrome, then the problem is very simple, no need to cut it, that is, dp[i] = 0;
- If s[0, i] is not a palindrome, we need to add a variable j, the range of j is (0, i], here are some boundary conditions of j, j must be greater than 0 The reason is that when j is 0, that is, there is no need to divide s[0, i] (that is, when s[0, i] is a palindrome), and when j is i, it is found in s[0, i-1] It does not start from 0 and is a palindrome. Using this j variable, we traverse j, j is less than or equal to i, then we know the value of dp[j-1]. If from j to i The string is a palindrome, then we make dp[i] = min(dp[i], dp[j – 1] + 1); traverse all the cases of j, we can find the minimum of dp[i] worth it.
3.1.3 Find out whether all substrings are palindrome strings in advance
This can also be known through the solution of the above problem.
3.2 Overall Code
class Solution {<!-- -->
public:
int minCut(string s) {<!-- -->
int n = s. size();
// Find out whether all substrings are palindrome strings
vector<vector<bool>> isPal(n, vector<bool>(n));
for (int i = n - 1; i >= 0; --i)
for (int j = i; j < n; + + j)
if (s[i] == s[j])
isPal[i][j] = i + 1 < j ? isPal[i + 1][j-1] : true;
// Create the dp table, since it is seeking the minimum value, you can first initialize all positions to the maximum
vector<int> dp(n, INT_MAX);
for (int i = 0; i < n; + + i)
{<!-- -->
if (isPal[0][i]) dp[i] = 0;
else
{<!-- -->
for (int j = 1; j <= i; + + j)
if (isPal[j][i]) dp[i] = min(dp[i], dp[j-1] + 1);
}
}
return dp[n-1];
}
};
4.【LeetCode】516. The longest palindrome subsequence
4.1 Idea explanation
4.1.1 Create dp table
This question uses the method of dynamic programming to create a two-dimensional dp table, dp[i][j] represents the length of the largest palindromic subsequence in s[i, j]. And we artificially stipulate that i must be less than or equal to j.
4.1.2 State transition equation
When finding dp[i][j], it is first necessary to judge whether s[i] and s[j] are the same.
if s[i] == s[j]
- If i == j, it means that the positions of i and j are the same, and at this time dp[i][j] is 1
- If i + 1 == j, it means that i is adjacent to j, and at this time dp[i][j] is 2
- In other cases, it means that there are other elements between i and j, then at this time dp[i][j] = dp[i + 1][j-1] + 2;
if s[i] != s[j]
Then at this time, it means that it cannot start with i and end with j at the same time. We can remove this situation and find a maximum subsequence. The method is to choose the largest one among dp[i + 1, j] and dp[i, j-1]. That is, dp[i][j] = max(dp[i + 1[j], dp[i][j-1]);
4.1.3 No need to consider boundary issues
When finding dp[i][j], we may use i + 1 and j – 1. When they may cross the boundary, it must be when i is equal to j. The dp table we created is two-dimensional. We can think that when it may cross the boundary, it is the position of the upper left corner or the lower right corner. But in fact, these two positions satisfy i == j, then dp[i][j ] will be directly assigned a value of 1, and i + 1 and j – 1 will not be used at this time, so we don’t need to consider the situation of crossing the boundary.
4.2 Overall code
class Solution {<!-- -->
public:
int longestPalindromeSubseq(string s) {<!-- -->
int n = s. size();
// Create a two-dimensional dp table, dp[i][j] represents the length of the largest subsequence of s[i, j]
vector<vector<int>> dp(n, vector<int>(n));
// dp[i][j] needs to use dp[i + 1][j-1]
// So i loops from large to small, j loops from small to large, and i is less than or equal to j
for (int j = 0; j < n; + + j)
{<!-- -->
for (int i = j; i >= 0; --i)
{<!-- -->
if (s[i] == s[j])
{<!-- -->
if (i == j) dp[i][j] = 1;
else if (i + 1 == j) dp[i][j] = 2;
else dp[i][j] = dp[i + 1][j-1] + 2;
}
else dp[i][j] = max(dp[i + 1][j], dp[i][j-1]);
}
}
return dp[0][n-1];
}
};
5. 【LeetCode】1312. The minimum number of insertions to make a string a palindrome
topic link
5.1 Idea explanation
5.1.1 Create dp table
Using the solution of dynamic programming, you can learn from the ideas of the above questions. Create a two-dimensional dp table, dp[i][j] represents the minimum number of operations from i to j to become a palindrome. (We artificially stipulate that i is less than or equal to j)
5.1.2 State transition equation
Similarly, we will discuss the cases of s[i] == s[j] and s[i] != s[j].
if s[i] == s[j]
- If i == j, then i and j have the same position at this time, a character itself is a palindrome, dp[i][j] = 0
- If i + 1 == j, then i and j have the same position at this time, and these two characters are also palindrome strings at this time, dp[i][j] = 0
- If i + 1 < j, then there are other characters between i and j at this time, dp[i + 1][j-1] is the minimum number of operations for the string between i and j to become a palindrome, because s[ i] == s[j], so after adding the characters at positions i and j, dp[i][j] = dp[i + 1][j-1].
If s[i] != s[j]
The characters at positions i and j are different, so just find the minimum value of dp[i + 1][j] and dp[i][j-1] at this time, and then add 1 to the smallest one, that is, dp [i][j] = min(dp[i + 1][j], dp[i][j-1]) + 1; It is equivalent to adding a s[i] or s[ j] The same character will do.
5.1.3 No need to consider boundary issues
This question is the same as the fourth question, and it needs to consider crossing the boundary. The specific reasons are the same as the fourth question.
When finding dp[i][j], we may use i + 1 and j – 1. When they may cross the boundary, it must be when i is equal to j. The dp table we created is two-dimensional. We can think that when it may cross the boundary, it is the position of the upper left corner or the lower right corner. But in fact, these two positions satisfy i == j, then dp[i][j ] will be directly assigned a value of 0, and i + 1 and j – 1 will not be used at this time, so we don’t need to consider the situation of crossing the boundary.
5.2 Overall Code
class Solution {<!-- -->
public:
int minInsertions(string s) {<!-- -->
int n = s. size();
// dp[i][j] indicates the minimum number of operations for s[i, j] to become a palindrome
vector<vector<int>> dp(n, vector<int>(n, INT_MAX));
// dp[i][j] needs to use dp[i + 1][j-1]
// So i should be traversed from big to small, and j should be traversed from small to large
// And i must be less than or equal to j, so the initial value of i is j
// Because the initial value of i is j, j is in the outer layer of the loop, and i is in the inner layer
for (int j = 0; j < n; + + j)
{<!-- -->
for (int i = j; i >= 0; --i)
{<!-- -->
if (s[i] == s[j])
dp[i][j] = i + 1 < j ? dp[i + 1][j-1] : 0;
else
dp[i][j] = min(dp[i][j-1], dp[i + 1][j]) + 1;
}
}
return dp[0][n-1];
}
};