javascript初探LeetCode之5.Longest P

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

example

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

分析

这是leetcode上的第5题，难度为Medium，是要找出给定字符串的最长回文子串，很容易想到有两种情况：

• 1、奇数长度的回文子串，以当前遍历元素为中心向两边扩散，比如题目给出的第一个例子
• 2、偶数长度的回文子串，以当前遍历元素和其后一位元素为中心，向两边扩散，比如题目给出的第二个例子。
  首先想到的是双重循环，首先是循环遍历字符串的每个字符，然后向两边扩散也需要一重循环。

js实现

不带注释版：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    var arr = s.split('');
    var start = 0, end = 0;
    for(let i = 0; i< arr.length; i++){
        for(let j = 1; j <= i && i + j < arr.length; j++){
            if(arr[i-j] == arr[i+j]){
                if( 2 * j > end - start){
                    start = i - j;
                    end = i + j;
                }
                else continue;
            }
            else break;
        }
        if(i < arr.length - 1 && arr[i] == arr [i+1]){
            if(end - start < 2){
                start = i;
                end = i + 1;
            }
            for(let j = 1; j <= i && i + j +1 < arr.length; j++){
                if(arr[i-j] == arr[i +j +1]){
                    if(2 * j + 2 > end - start +1){
                        start = i - j;
                        end = i + j + 1;
                    }
                    else continue;
                }
                else break;
            }
        }
    }
    return s.substring(start,end + 1);
};

带注释版：

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    var arr = s.split('');//转成数组,直接对s进行操作并不会缩短执行时间
    var start = 0, end = 0;//记录回文串起始
    for(let i = 0; i< arr.length; i++){//遍历s
        for(let j = 1; j <= i && i + j < arr.length; j++){//注意边界，i-j不超出左边界，i+j不超出右边界
            if(arr[i-j] == arr[i+j]){//对称字符相等
                if( 2 * j > end - start){//判断是不是最长
                    start = i - j;
                    end = i + j;
                }
                else continue;//不是就跳下次循环
            }
            else break;//对称字符一旦不同，跳出循环
        }
        if(i < arr.length - 1 && arr[i] == arr [i+1]){//回文串长度为偶数时
            if(end - start < 2){//在上面if里已经有对称相同的字符了，就需要看需不需要改写start、end
                start = i;
                end = i + 1;
            }
            for(let j = 1; j <= i && i + j +1 < arr.length; j++){//循环向两边扩散，注意边界
                if(arr[i-j] == arr[i +j +1]){//对称字符相同
                    if(2 * j + 2 > end - start +1){//判断是不是最长
                        start = i - j;
                        end = i + j + 1;
                    }
                    else continue;//不是就跳下次循环
                }
                else break;//对称字符一旦不同，跳出循环
            }
        }
    }
    return s.substring(start,end + 1);//返回最长回文子串
};

总结

求解最长回文子串思路还是很清晰的，注意一下边界就行，还有就是js中substring(start, end)函数是截取的字符串包括index=start的元素，但不包括index=end的元素，所以return时，end+1了。