“This is the 23rd day of my participation in the First Challenge 2022. For details: First Challenge 2022”

Hope is a good thing, maybe the best of things. And no good thing Ever dies.

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"Copy the code

Source: LeetCode

Subject analysis

Central diffusion method

  1. Analysis of the
  • For strings, each character can act as the center of a palindrome string (the center of a palindrome string means spreading out from the middle to the sides)
  • Since each character can be the center of a palindrome, there are odd and even palindrome strings
  • Each character of the string is iterated over, taking the longest of odd and even palindromes, respectively
  1. Code implementation
/** * @param {string} s * @return {number} */ var longestPalindrome = function (s) {// /** ** @param {*} s * @param {*} l left boundary * @param {*} r right boundary */ let palindrome = (s, l, R) = > {while && (l > = 0 r < s.l ength && s [l] = = s [r]) {/ / to a l - both sides; r++; } return s.substr(l + 1, r-L-1); return s.substr(l + 1, r-L-1); }; let res = ""; for (let i = 0; i < s.length; I ++) {// let s1 = palindrome(s, I, I); Let s2 = palindrome(s, I, I +1); let s2 = palindrome(s, I, I +1); res = res.length > s1.length ? res : s1; res = res.length > s2.length ? res : s2; } return res; };Copy the code
  1. Complexity analysis

Time complexity: O(n^2), space complexity: O(1).

About pointer

  1. Analysis of the

If it is a substring, the elements on the left and right sides must be symmetrical, so we can use the left and right Pointers to spread out from the current element to find the longest string.

  1. Code implementation
function longestPalindrome(s: string): string { let res = ''; for (let i = 0; i < s.length; Const s1 = palindrome(s, I, I); const s1 = palindrome(s, I, I); const s1 = palindrome(s, I, I); Const s2 = palindrome(s, I, I + 1); const s2 = palindrome(s, I, I + 1); res = res.length > s1.length ? res : s1; res = res.length > s2.length ? res : s2; } return res; }; Function palindrome(s, l, r) {function palindrome(s, l, r) {while (l >= 0 &&r < s.length &&s [l] == s[r]) {l--; r++; } return s.substr(l + 1, r - l - 1); }Copy the code
  1. Complexity analysis

Time complexity: O(n^2), space complexity O(1).

conclusion

If this article helped you, please like 👍 and follow ⭐️.

If there are any errors in this article, please correct them in the comments section 🙏🙏

Welcome to pay attention to my wechat public number, exchange technology together, wechat search 🔍 : “fifty years later”