c++ - 如何降低这个子串回文的时间复杂度?
问题描述
我正在解决这个问题,输入:一个字符串,输出:它是最长的子字符串,它是一个回文我以 O(n^3) 中的以下方式解决了它。我试图在 O(n^2) 中解决它。请帮忙。这是代码:
int isPalindrome(string str){
for(int i = 0, j = str.size()-1 ; i < j ;i++,j--){
if(str[i] != str[j])
return 1; //1 is the minimal palindrome length
}
return str.size();// return length of palindrome
}
string longestPalindromicSubstring(string str) {
int maxLength = 0;
string result = "";
for(int i = 0; i < str.size(); i++){
for(int j = 1; j <= str.size(); j++){
string temp = str.substr(i,j); //substring of length j
if(temp.size() > maxLength){
int count = isPalindrome(temp);
if(count>maxLength){
maxLength = count;
result = temp; //saving the substring as result
}
}
}// j for loop ends
} //i loop ends
return result;
}
解决方案
pair<int,int> getPalindromeRange(string str, int left, int right){
while(left>=0 && right<str.length()){
if(str[left] != str[right])
break;
left--;
right++;
}
return make_pair(left+1, right);
}
string longestPalindromicSubstring(string str) {
pair<int,int>longestRange{0,1};//first value is starting index and second value is the length of the substring
string result ="";
for(int i=1 ;i<str.length(); i++){
pair<int,int>odd = getPalindromeRange(str, i-1, i+1);
pair<int,int>even = getPalindromeRange(str, i-1, i);
if(longestRange.second - longestRange.first < odd.second - odd.first)
longestRange = odd;
if(longestRange.second - longestRange.first < even.second - even.first)
longestRange = even;
if (longestRange.second - longestRange.first == str.length())
break;
}//for loop ends
result = str.substr(longestRange.first, longestRange.second -longestRange.first);
return result;
}
推荐阅读
- python - python matplot图上未显示时间戳
- c - 无法将文本文件转换为二进制文件
- javascript - 对于 Jest 测试用例,'globalThis' 被低估了
- javascript - 如何在图像更改时暂停音频 onmouseout
- firebase - 使用带有 Vue Js 的 Firebase 云功能发送电子邮件时出错
- javascript - 如何同步多个handsontable水平滚动
- java - 使用“ImageIO.read”读取图像路径以显示在 JLabel 中
- jestjs - NestJs:单元测试如何模拟函数条件或有许多返回案例
- google-apps-script - saveAndClose() 是无法识别的文件类型
- python - 使用 pd.merge 复制 pd.concat