Title description:

Given an integer x, return true if x is a palindrome integer; Otherwise, return false.

Palindromes are integers that read in positive (left to right) and backward (right to left) order. For example, 121 is palindrome and 123 is not.

Example 1:

Input: x = 121 Output: trueCopy the code

Example 2:

Input: x = -121 Output: false Description: Read from left to right. The value is -121. Read from right to left, 121-. So it's not a palindrome number.Copy the code

Example 3:

Input: x = 10 Output: false Description: Read from right to left, 01. So it's not a palindrome number.Copy the code

Example 4:

Input: x = -101 Output: falseCopy the code

Solution:

For palindrome numbers or palindrome strings, it can be understood that a string read forward is the same as a string read backwards.

For example: abcba, the result is: a->b->c->b->a, the result is: A <-b<-c<-b<-a, they have the same result.

For example: Shanghai tap water from the sea is also a palindrome string.

The string is first converted to an array of characters, and then you can use the idea of comparing the first and last elements to determine whether they are equal or not.

/ * * *@param {number} x
 * @return {boolean}* /
var isPalindrome = function(x) {
    // Special circumstances
    if (x < 0) return false
    if (x == 1) return true

    x = x.toString()

    var mid = parseInt(x.length/2) // Do not iterate through all, just to the middle element, since the latter is already compared
    for (var i = 0 ; i < mid ; i++) {
        if(x[i] ! = x[x.length-1-i]) {// Compare the first and last elements
            return false}}return true
};
Copy the code

Now that we know about palindrome strings, let’s look at the problem of finding the longest substring of a string.

Topic describes

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

Example 2:

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

Example 3:

Input: s = "a" Output: "a"Copy the code

Example 4:

Input: s = "AC"Copy the code

Solution:

First of all, we need to understand the definition of a substring: a contiguous substring in a string, such as abcde, where ABC is a substring, abcd is a substring, and ac or BD are not, because they are not contiguous.

At the same time, through the idea of the previous problem, we can easily get a violent solution, that is, enumerate all the substrings of the changed string, and then judge whether they are palindromic strings respectively, while recording the length, take the maximum length of the result, we can get the following solution:

/ * * *@param {string} s
 * @return {string}* /
var longestPalindrome = function(s) {
    // A single character must be a palindrome string
    if (s.length == 1) return s
    // Check whether it is a palindrome string
    var check = function(str){
        var mid = parseInt(str.length/2)

        for (var i = 0 ; i < mid ; i++) {
            if(str[i] ! = str[str.length-i-1]) {
                return false}}return true

    }
    var res = ' '
    // Enumerates all substrings
    for (var i = 0 ; i < s.length ; i++) {
        var cur = s[i]
        for (var j = i+1 ; j < s.length ; j++) {
            cur = cur + ' ' + s[j]
            if (check(cur)) {

                if (cur.length > res.length) { // Take the larger value of the length each time
                    res = cur
                }
            }
        }
    }

    return res == ' ' ? s[0] : res
};
Copy the code

The above solution can pass, but it is very inefficient. By observing the characteristics of palindrome strings, we can know that for a substring, if it is a palindrome string and its length is greater than 2, it is still a palindrome string after removing the first and last two letters. For example, with the string ababa, if we already know bab is a palindrome string, then ababa must be a palindrome string because it starts and ends with both letters a.

Create a dynamically programmed array dp[] :

  • dp[i][j]Representation strings[i]tos[j]Is the palindrome string between.
  • And if thes[i] == s[j],dp[i][j]= =dp[i+1][j-1], that is, if the first element is the same, it is still a palindrome string after removing the first element.
  • After each updatedp[i][j]After that, update and record the maximum value.

The code is as follows:

var longestPalindrome = function(s) {
    let n = s.length;
    let res = ' ';
    let dp = Array.from(new Array(n),() = > new Array(n).fill(0));
    // Consider that the main recursion relation is given by the substring I +1.. In the case of J-1, recursively to I.. Therefore, the iterative process needs to iterate variable I in reverse order and j in positive order
    for(let i = n-1; i >=0; i--){for(letj = i; j < n; j++){//(j-i < 2) a single character must be a palindrome string
            //dp[I +1][j-1] and s[I] == s[j
            if (s[i] == s[j] && (j - i < 2 || dp[i+1][j-1])) {
                dp[i][j] = true
            }
            // if dp[I][j] is a palindrome, the maximum value (j - I +1) indicates the length
            if(dp[i][j] && j - i +1 > res.length){
                res = s.substring(i,j+1); }}}return res;
};
Copy the code