如何降低这个子串回文的时间复杂度?
How do I reduce time complexity of this substring palindrome?
我正在解决这个问题,输入:一个字符串,输出:它是回文的最长子串
我在 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;
}
我正在解决这个问题,输入:一个字符串,输出:它是回文的最长子串 我在 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;
}