leetcode 5 Longest Palindromic Substring Java & JavaScript解法

发布时间:2019-11-19 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了leetcode 5 Longest Palindromic Substring Java & JavaScript解法脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

题目详情

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.
Example:
Input: "cbbd"
Output: "bb"

想法

  • 这道题一个比较好的想法是以遍历到的每个元素为起始点,向两边扩展,直到找到满足以这个元素为中心的最长回文字符串。
  • 因为这种想法没次都是两边同时扩展。所以要分目标字符串长度为奇数、目标字符串为偶数两种情况。进行两次扩展。

Java解法

    PRivate int maxLen,low;          public String longestPalindrome(String s){         int length = s.length();         if(length < 2)return s;                  for(int i=0;i<length-1;i++){             extendPalindorme(s,i,i);             extendPalindorme(s,i,i+1);         }         return s.substring(low,low+maxLen);     }          public void extendPalindorme(String s,int begin,int end){         while(begin >= 0 && end < s.length() && (s.charAt(begin)== s.charAt(end))){             begin --;             end ++;         }         if(maxLen < end-begin-1){             low = begin+1;             maxLen = end-begin-1;         }     }

javaScript解法

  • 这里面我用的是全局变量。没次还要重新赋值,感觉有点蠢=..=
/**  * @param {string} s  * @return {string}  */ var maxLen = 0; var low = 0;  var longestPalindrome = function(s) {     var length = s.length;     if(length < 2){         return s;     }      for(var i=0;i<length-1;i++){         extendPalindrome(s,i,i);         extendPalindrome(s,i,i+1);      }     let res = s.substring(low,low+maxLen);     low =0;maxLen= 0;     return res;   }; function  extendPalindrome(s,start,end){      while(start >= 0 && end < s.length && (s[start] == s[end])){         start --;         end ++;      }     if(maxLen < end-start - 1){         low = start + 1;         maxLen = end-start-1;     } } 

脚本宝典总结

以上是脚本宝典为你收集整理的leetcode 5 Longest Palindromic Substring Java & JavaScript解法全部内容,希望文章能够帮你解决leetcode 5 Longest Palindromic Substring Java & JavaScript解法所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。