5. The longest subroutine string

Given a string s, find the longest subroutine in s. You can assume that the maximum length of s is 1000.

Example 1:

Input: "babad" Output: "bab"Copy the code

Note: “ABA” is also a valid answer. Example 2:

Input: "CBBD" Output: "bb"Copy the code

Answer:

Problem reading, find the longest loop substring in the string. A substring is a symmetric string.

Dynamic planning :(segmentation of small problems, continuous execution. Find the optimal solution)

  • Create a two-dimensional array. Default is false.
  • When encountering palindromes, save the state true;
  • Judge whether there are palindromes behind the short palindromes according to the front;
  • Stores the longest string.
var longestPalindrome = function(s) { 
	let dp = Array.from({length: s.length}, () = > new Array(s.length).fill(false));
  let res = "";
  for(let i=0; i<s.length; i++) {
    // Look ahead from the iterated string
    for(let j=i; j>=0; j--) {
      //s[I]===s[j], i-j<2 check whether the two strings are consecutive
      // Determine whether the preceding small range is palindrome, infer whether the following can be palindrome
      dp[j][i] = s[i]===s[j] && (i-j<2 || dp[j+1][i-1]); 
      if(dp[j][i] && i-j+1 > res.length) {
        res = s.substring(j, i+1); }}}return res;
}
Copy the code