题目
Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
思路一
即不使用技巧,穷举所有可能。时间复杂度为O(n^3)(时间上最长,不推荐使用),空间复杂度为O(1)。本思路是从最大长度的字串开始,而不是从最小开始。假如说给定的字符串为size,先遍历长度为size的字串是否为回文串,如果是停止,如果不是遍历长度为size-1的字串是否是回文串,一次类推。
代码一
#include <iostream>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
for(int i = size;i > 0;--i){
for(int start = 0;start + i <= size;++start){
bool result = IsPalindromeSubNumber(s.substr(start,i));
if(result){
return s.substr(start,i);
}
}
}
return "";
}
private:
bool IsPalindromeSubNumber(string num){
int len = num.length();
for(int i = 0,j=len-1;i < j;i++,j--){
if(num[i] != num[j]){
return false;
}
}
return true;
}
};
int main(){
Solution s;
string num = "flsuqzhtcahnyickkgtfnlyzwjuiwqiexthpzvcweqzeqpmqwkydhsfipcdrsjkefehhesubkirhalgnevjugfohwnlhbjfewiunlgmomxkafuuokesvfmcnvseixkkzekuinmcbmttzgsqeqbrtlwyqgiquyylaswlgfflrezaxtjobltcnpjsaslyviviosxorjsfncqirsjpkgajkfpoxxmvsyynbbovieoothpjgncfwcvpkvjcmrcuoronrfjcppbisqbzkgpnycqljpjlgeciaqrnqyxzedzkqpqsszovkgtcgxqgkflpmrikksaupukdvkzbltvefitdegnlmzeirotrfeaueqpzppnsjpspgomyezrlxsqlfcjrkglyvzvqakhtvfmeootbtbwfhqucbnuwznigoyatvkocqmbtqghybwrhmyvvuchjpvjckiryvjfxabezchynfxnpqaeampvaapgmvoylyutymdhvhqfmrlmzkhuhupizqiujpwzarnszrexpvgdmtoxvjygjpmiadzdcxtggwamkbwrkeplesupagievwsaaletcuxtpsxmbmeztcylsjxvhzrqizdmgjfyftpzpgxateopwvynljzffszkzzqgofdlwyknqfruhdkvmvrrjpijcjomnrjjubfccaypkpfokohvkqndptciqqiscvmpozlyyrwobeuazsawtimnawquogrohcrnmexiwvjxgwhmtpykqlcfacuadyhaotmmxevqwarppknoxthsmrrknu";
cout<<s.longestPalindrome(num)<<endl;
return 0;
}
思路二
假设现在已经遍历到第 i 个字符,要找出以该字符为“中心”的最长对称字符串,我们需要用另两个指针分别向前和向后移动,直到指针到达字符串两端或者两个指针所指的字符不相等。因为对称子字符串有两种情况,所以需要写出两种情况下的代码:
(1) 第 i 个字符是该对称字符串的真正的中心,也就是说该对称字符串以第 i 个字符对称, 比如: “aba”
(2)第 i 个字符串是对称字符串的其中一个中心。比如“abba”。
所以遍历到每个字符都要考虑两种情况,它可能是在奇数个回文串中或者是在偶数个回文串中
代码二
#include <iostream>
using namespace std;
class Solution {
public:
string longestPalindrome(string str) {
int Max = 0,startIndex = 0;
int size = str.size();
int left,right;
for(int i = 0;i < size;i++){
int oddLen = 1;
left = i-1;
right = i+1;
while(left >= 0 && right < size && str[left] == str[right]){
left--;
right++;
oddLen += 2;
}
if(oddLen > Max){
Max = oddLen;
startIndex = left+1;
}
left = i;
right = i+1;
int evenLen = 0;
while(left >= 0 && right < size && str[left] == str[right]){
left--;
right++;
evenLen += 2;
}
if(evenLen > Max){
Max = evenLen;
startIndex = left+1;
}
}
return str.substr(startIndex,Max);
}
};
int main(){
Solution s;
string num = "abbad";
cout<<s.longestPalindrome(num)<<endl;
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 12. Integer to Roman 13. Roman to Integer 14. Longest Common Prefix 15. 3Sum 20. Valid Parentheses 21. Merge...
5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 10.Regular Expression Matching 11.Container With Most Water 12...
LongestPalindromicSubstring.java 5. Longest Palindromic Substring │ RansomNote.java //383. Ransom Note │ RussianDollEnvelope.java //354. Russian Doll Envelopes │ SlidingWindowMaximum.java //239. ...
Palindromic Substring 006. ZigZag Conversion 007. Reverse Integer 008. String to Integer 009. Palindrome Number 010. Regular Expression Matching 011. Container With Most Water 012. Integer to Roman ...
5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122.Best Time to Buy and Sell ...
Longest-Palindromic-Substring(最长回文子串) 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 Sample 1 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 Sample 2 输入...
5.Longest Palindromic Substring 6.ZigZag Conversion 7.Reverse Integer 8.String To Integer 9.Palindrome Number 10.String To Integer 11.Container With Most Water 12.Integer To Roman 13.Roman To Integer ...
最长回文:5. Longest Palindromic Substring - 字数组余数:523. Continuous Subarray Sum - 无重复字符的最长子串:3. Longest Substring Without Repeating Characters - 最小跳跃步数问题 - 动态规划 + 循环策略...
Palindromic Substring 最长回文子串 6. ZigZag Conversion Z字型变换 7. Reverse Integer 整数反转 8. String to Integer (atoi) 字符串转换整数 (atoi) 9. Palindrome Number 回文数 10. Regular Expression ...
Palindromic Substring: Learning "Manacher" algorithm. tips:substr(start_position,lens) 6. ZigZag Conversion: Find the Regulation. 11. Container With Most Water 问题简述:给出一个list a,找到一组i,j使得...
Palindromic Substring 最长回文子串,补符号,记忆 6. ZigZag Conversion 观察规律 7. Reverse Integer 翻转整数 8. String to Integer 解析字符串 9. Palindrome Number 回文数字 10. Regular Expression Matching...
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 Example 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. Example 2: ...
5.Longest Palindromic Substring 解决这类 “最优子结构” 问题,可以考虑使用 “动态规划”: 1、定义 “状态”; 2、找到 “状态转移方程”。 记号说明: 下文中,使用记号 s[l, r] 表示原始字符串的
最大公共字符串leetcode 最长回文子串 给定一个字符串 s,找出 s 中最长的回文子串。 您可以假设 s 的最大长度为 1000。 示例 1: Input: "babad" Output: "bab" Note: "aba" is also a valid answer. 示例 2: ...
leetcode 516 8/13 - 8/18 周:leetcode#: 409. longestPalindrome 125. ...5. Longest Palindromic Substring option: 516. Longest Palindromic Subsequence string replacement strStr II 链接:
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
leetcode 不会 此项目用于记录本人leetcode刷题的代码 2. Median of Two Sorted Arrays Star 暴力解法, apparently won't be ...5. Longest Palindromic Substring Dynamic Programming p[i][j] =
leetcode数组下标大于间距 5. Longest Palindromic Substring 这里使用menecher方法,就是动态规划,首先在原先的字符串之间插入'#, 这样可以统一处理奇数串和偶数串, 使用两个变量纪录状态, far_pos表示最长回文...
Substring.cpp │ └── python │ ├── 001 - Two Sum.py │ ├── 002 - Add Two Numbers.py │ ├── 003 - Longest Substring Without Repeating Characters.py │ ├── 004 - Median of Two ...