LeetCode.5 最长回文子串(longest-palindromic-substring)(J

Steven 发布于2019-08-23 16:47 / 2133人阅读

摘要：一题目最长回文子串给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。

一、题目

最长回文子串：

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

二、我的答案

思路

1.排除法，最优解法肯定不是暴力遍历
2.紧接着想到第三题中使用的两个指针同步遍历一个字符串的方法，尝试了一下，发现跟暴力遍历没有区别
3.再看几遍题，要找的是回文字符串，回文字符串的特点在于两边字符都相同，也就是说需要找的是两边字符都相同中间点(注意是中间点而不是中间字符，因为题干中例1的中间点是a，但是例2的中间点是bb)

代码

v1.0(过于丑陋，可跳过直接看说明和v2.0)

   /**
    * @param {string} s
    * @return {string}
    */
    var longestPalindrome = function(s) {
     function expendString(index1, index2) {
       if(index1 > 0 && index2 + 1 < s.length &&s[index1 -1] === s[index2 + 1]){
         return expendString(index1 -1, index2 + 1)
       } else {
         return [index1, index2, index2 - index1]
       }
     }
     let longestArr = [0, 0, 0]
     let tempArr
     for(let i = 1; i< s.length; i++) {
       if(i + 1 < s.length&&s[i-1] === s[i+1]) {
         tempArr = expendString(i-1, i+1)
         tempArr[2] > longestArr[2] ? longestArr = tempArr : null
       }
       if(s[i -1] === s[i]) {
         tempArr = expendString(i - 1, i)
         tempArr[2] > longestArr[2] ? longestArr = tempArr : null
       }
     }
     return s.slice(longestArr[0], longestArr[1] + 1)
   };

讲解

1. 函数expendString作用为以两个传参拓展字符串，判断是否依然是回文字符串

2. 数组longestArr作用为防止当前最长字串的两个下标和长度(我也不知道当时自己为什么还要费劲写个数组)

3. for循环中判断回文串的中点是一个("aba")还是两个("abba"),然后分别调用上文定义的expendString函数进行拓展

通过，下一步要做的就是优化成能看懂的版本

v2.0

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s){
  function expendString(index1, index2) {
    if (index1 >= 0 && index2 < s.length && s[index1] === s[index2]) {
      expendString(index1 - 1, index2 + 1)
    } else {
      index2 - index1 > longestString.length ?
        longestString = s.slice(index1 + 1, index2) :
        null
    }
  }
  let longestString = s[0] || ""
  for (let i = 1; i < s.length; i++) {
    if (i + 1 < s.length) {
      expendString(i - 1, i + 1)
    }
    if (s[i - 1] === s[i]) {
      expendString(i - 1, i)
    }
  }
  return longestString
};

云服务器私有云 java最长相同子串最长公共子串 java回文程序 java公共子串

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103288.html

LeetCode代码分析——5. longest-palindromic-substring（动态规

摘要：题目描述给定一个字符串，找到中最长的回文子串。你可以假设的最大长度为。示例输入输出注意也是一个有效答案。示例输入输出思路分析暴力解法解决一个问题如果没有思路，就要想办法从简单粗暴的解法开始，然后想办法优化它。题目描述 https://leetcode-cn.com/probl... 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1： ...

neuSnail 2019-08-19 10:35 评论0 收藏0
[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

摘要：第一种方法常规方法。如果不存在公共前缀，返回空字符串。注意假设字符串的长度不会超过。说明本题中，我们将空字符串定义为有效的回文串。示例输入输出一个可能的最长回文子序列为。数值为或者字符串不是一个合法的数值则返回。说明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站点：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 评论0 收藏0
Leetcode 5 Longest Palindromic Substring 最长回文子串

摘要：难度题目是说给出一个字符串求出这个字符串的最长回文的子串回文是指前后完全对称的字符串像是之类的都算是回文奇数字母的回文和偶数字母的回文中心是不一样的奇数字母比如的中心在中间字母上偶数字母比如的回文在中间两字母的中心上由此可见回文中心点实际上 Given a string s, find the longest palindromic substring in s. You may as...

NotFound 2019-08-14 17:12 评论0 收藏0
最长回文子串——Manacher 算法

摘要：问题定义最长回文子串问题给定一个字符串，求它的最长回文子串长度。可以采用动态规划，列举回文串的起点或者终点来解最长回文串问题，无需讨论串长度的奇偶性。 0. 问题定义最长回文子串问题：给定一个字符串，求它的最长回文子串长度。如果一个字符串正着读和反着读是一样的，那它就是回文串。下面是一些回文串的实例： 12321 a aba abba aaaa tatt...

mingzhong 2019-07-24 18:10 评论0 收藏0
获取最长回文子串

摘要：以下是最长回文子串的相关代码，相关逻辑已在注释中注明我们原有的字符串可能存在两种回文子串，一种是具有基数个元素例如一种是具有偶数个元素例如这样的话分情况判断比较复杂所以我们对原字符串进行扩充在相邻元素中插入特殊值插入后的原基数回文子串变成了以下是最长回文子串的Manacher‘s Algorithm相关代码，相关逻辑已在注释中注明： public static String solu...

ymyang 2019-08-19 11:46 评论0 收藏0