There was a LeekCode competition last night. Five questions were solved in two and a half hours. After solving the first two questions easily, I got stuck on the third question. When there was half an hour left, I gave up and started to solve the fifth question. But the verification was not passed, the fourth question only looked at the next question.
The No. 1 boss wrote it all in 36 minutes.
There is a big gap, and I can only get closer to the boss little by little.
LeekCode—5. Longest palindrome substring
Given a string s, find the longest palindrome substring in s. You can assume that the maximum length of s is 1000.
Question-solving ideas: There are several ways to solve this problem. Let me talk about my own ideas for solving this problem (center extension). First, palindromes are divided into three categories: 1: ‘baab’; 2: ‘bab’; 3: ‘a’. Then, it is obvious that the palindrome is symmetrical from the center (the first two are easy to understand, and the third only appears in fields like’abcd’. Each character can be regarded as a palindrome, just take it The first character is his palindrome). We traverse this field, taking each character as the center of the palindrome, and compare the first and second cases respectively: the length of the first palindrome is an even number, because it is traversed, so we only compare the current position with him Whether the previous characters are the same, if they are the same, continue to compare whether the characters before and after them are the same; the length of the second palindrome is odd, you need to add its own length when calculating its length, and then compare whether the characters before and after are the same. When there are multiple repeated characters, both conditions will be satisfied (such as ‘baaab’), so each character needs to perform both odd and even numbers at the same time, and then take the larger length.
var longestPalindrome = function(s) {if(s.length<2){ return s;} let length=0; let string=''; for(let i=1 ;i
This question officially provides a lot of solutions, and I have considered the way to reverse the string. , Because this is the most time-saving, but I tried many times how to intercept strings for comparison, and finally gave up. As for brute force cracking, it traverses all possible strings and then judges whether it is a palindrome. I think this is very stupid, and I think expanding from the center is actually a brute force cracking in a certain sense. There is no need to list all the strings before comparing them. I'm not very familiar with the dynamic programming algorithm, and I don't understand it for the time being. I will come back and add it when I can understand it later. There is also a Manacher algorithm, which is said to be very awesome. I will study it first and come back to make up later.