This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

Longest string of subroutines

Given a string s, find the longest substring in s.

LeetCode hot question 100, the fifth question is also a very easy to appear in the front-end interview algorithm. Propositional keywords: string, dynamic programming

The low pass rate makes everyone flinch. Learning the front end, we not only have artistic thinking, but also have exquisite logic, and this problem, can let us experience some practice.

* * sample1Enter: s ="babad"Output:"bab"Explanation:"aba"It is also the answer to the question. * * sample2Enter: s ="cbbd"Output:"bb"

Copy the code

So let’s start.

Give up thinking and respect instinct

Direct violence

Define two Pointers I and j, use these two Pointers to nested two-layer loops, try to enumerate all possible subsequences corresponding to a given string, judge whether each subsequence is palindrome: if palindrome and the length has exceeded the current maximum length, update the maximum length, and record the two endpoints of the substring. When all substring enumerations are complete, we have the maximum length of the substring.

// It is recommended to skip
var longestPalindrome = function(s) {
    function isPalindrome(str) {
    var len  = str.length
    var middle = parseInt(len/2)
    for(var i = 0; i<middle; i++){if(str[i]! =str[len-i-1]) {return false}}return true
    }
    var ans = ' ';
    var max = 0;
    var len = s.length
    for(var i = 0; i<len; i++){for(var r = i+1; r<=len; r++){var tmpStr = s.substring(i,r)
            if(isPalindrome(tmpStr) && tmpStr.length > max){ ans = s.substring(i,r) max = tmpStr.length; }}}return ans;
};
Copy the code

But we have to be elegant. Violence is not the only solution.

Stop acting like a jerk and start thinking

The word ‘longest’ in the stem of the problem, when you see the maximum value, you have to start thinking about dynamic programming. And given a string, if the string is a palindrome string, then the longest palindrome string would be itself, and it would have 1/2 the length of the palindrome string inside.

So here’s the idea.

  1. Take the most central point as the core, set two Pointers continuously diverging to both sides, we can judge each diverging string, so as to find the palindrome string formed by this point
  2. So let’s diverge, let’s take each point as the center point, let’s start diverging, and then we can get the palindrome string at each point.
  3. At this point, it’s just code repetition, solving boundary problems and minor bugs through trial and error.

Although I am not the smart one, I like to learn from the experience of others and always learn from solving problems.

/ * * *@param {string} s
 * @return {string}* /
var longestPalindrome = function(s) {
        if (s.length<2) {return s
        }
        let res = ' '
        for (let i = 0; i < s.length; i++) {
            // The length of the substring is odd
            helper(i, i)
            // The length of the substring is even
            helper(i, i + 1)}function helper(m, n) {
            while (m >= 0 && n < s.length && s[m] == s[n]) {
                m--
                n++
            }
            // Notice that the values of m and n are exactly at the moment when the loop condition is not satisfied
            // The distance between m and n is n-m+1, but the distance between m+1 and n-1 should be n-m-1
            if (n - m - 1 > res.length) {
                // Slice also takes the interval m+1,n-1
                res = s.slice(m + 1, n)
            }
        }
        returnres }; Qing-Chen-4A//leetcode-cn.com/problems/longest-palindromic-substring/solution/chao-jian-dan-de-zhong-xin-kuo-san-fa-yi-qini/Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.Copy the code

This is the big guy’s solution, and it’s the best one I’ve ever done. I’ve learned it, and MAYBE I’ll forget it, but my blog will record my thoughts forever.

“Welcome to the discussion in the comments section. The excavation authorities will draw 100 nuggets in the comments section after project Diggnation. See the event article for details.”