脚本宝典收集整理的这篇文章主要介绍了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,请注明来意。