Reflections on a difficult leetcode
A few days ago, leetcode’s difficulty level question of the day once again made me feel that the real smart people are good at converting difficult problems into simple problems, rather than going great lengths.
Link to the purpose of this question: https://leetcode-cn.com/problems/shortest-palindrome/solution/
Topic
Given a string s, you can convert it to a palindrome by adding characters in front of the string. Find and return the shortest palindrome string that can be converted in this way.
** Example 1: **
1 | Enter: "aacecaaa" |
** Example 2: **
1 | Enter: "abcd" |
Problem-solving ideas
I don’t know if there are any friends who will be like me. If you use too much bfs, dfs, dp, etc., you will consider in that direction, but after thinking for a long time, it seems that there is no good way, so I went to look at the solution and suddenly realized.
Learn to transform the problem
Simply put, it is to find the longest palindrome prefix s’ of the existing string s, then put the remaining s - s’ in reverse order at the beginning of s, which is the shortest palindrome string.
This is the specific official proof logic: https://leetcode-cn.com/problems/shortest-palindrome/solution/zui-duan-hui-wen-chuan-by-leetcode-solution/
In this way, a problem of finding the shortest palindrome string becomes a simple problem of finding the longest palindrome prefix. When I saw this, I really had a feeling of enlightenment.
The next step is simple, how to retrieve the text prefix.
Find the longest palindrome prefix
Violence Act
The simplest brute force solution can determine whether the substring starting from 0 to i is palindromic, and i is from s.length - 1 to 0.
KMP algorithm
The KMP algorithm is used to calculate the overlap between two strings.
Assuming that the flashback of string s is s’, the overlap obtained by the KMP algorithm should be the longest palindrome prefix of s.
KMP algorithm
For the explanation of the KMP algorithm,阮一峰老师的这篇博客 speaks more clearly
If there is any doubt, it may be why: shift bits = number of characters matched - corresponding partial match value
So we need to understand:
What does the partial match value represent?
- “Partial match value” is the length of the longest common element of “prefix” and “suffix”. Take “ABCDABD” as an example,
- The prefix and suffix of “A” are both empty sets, and the length of the common elements is 0;
- “AB” is prefixed with [A] and suffixed with [B], and the length of the common element is 0;
- “ABC” prefixed with [A,
- “ABCD” is prefixed with [A,
- “ABCDA” is prefixed with [A,
- “ABCDAB” is prefixed with [A,
- “ABCDABD” is prefixed with [A,
The essence of “partial match” is that sometimes there are duplicates at the head and tail of the string. For example, if there are two “ABs” in “ABCDAB”, then its “partial match value” is 2 (the length of “AB”). When the search term moves, the first “AB” is moved back 4 bits (string length - partial match value) to reach the position of the second “AB”.
- Assuming that the number of matched characters is m, it means that the first m bits of the pattern string are the same as [i, i + m - 1] of the matched string, and i is the position where the match began.
In this case, the partial match value is n, which means that the first n bits of the pattern string are the same as the last n bits of [i, i + m - 1].
So moving m - n bits can skip over to match bits that cannot be the same.
Reference link:
https://leetcode-cn.com/problems/shortest-palindrome/
https://www.cxyxiaowu.com/2665.html
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html