javascript初探LeetCode之5.Longest P

作者: ThereThere_0d70 | 来源:发表于2017-07-14 15:29 被阅读0次

题目

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了。

相关文章

网友评论

    本文标题:javascript初探LeetCode之5.Longest P

    本文链接:https://www.haomeiwen.com/subject/acznhxtx.html