GFG字符串回文题运行超时 如何优化对应C++代码

报错信息 #

Test Cases Passed: 10000 / 10100
Time Limit Exceeded
程序运行耗时超出预期，预期时间限制为3.4秒，请优化代码后重新提交。

原实现代码 #

// { Driver Code Starts
 
#include <bits/stdc++.h>
using namespace std;


 // } Driver Code Ends
//User function template for C++
class Solution
{
    public:
    int helper(string s, int start, int end){
        
        if(start>=end)
        {                     //base cond.
            return 1;
        }
        if(s[start]!=s[end])
        {                     //small work
            return 0;
        }
        
        return helper(s, start+1,end-1);  
        
    }
    
int isPalindrome(string S)
{
    int n=S.size()-1;
    return helper(S, 0, n);
    }
};
// { Driver Code Starts.

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
   
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s;

        Solution ob;

        cout << ob.isPalindrome(s) << "\n";
    }

    return 0;
}  // } Driver Code Ends

超时根因与优化方向 #

• 核心性能问题来自递归函数的值传递传参：helper函数的入参s是值类型，每次递归调用都会完整拷贝一份整个输入字符串，当测试用例多、字符串长度大时，海量无意义的内存拷贝会直接耗尽时间配额。仅需要把参数修改为常量引用const string& s，不需要改动其他逻辑，就能消除90%以上的额外开销，基本可以通过所有用例。
• 递归实现存在固有额外开销：每次递归调用都需要创建、销毁函数栈帧，对于超长字符串，递归深度过高还可能触发栈溢出，性能上限低于迭代实现。最优写法是直接使用双指针迭代实现，无额外函数调用开销，时间复杂度O(n)、空间复杂度O(1)，是回文判断的标准最优实现。

优化后参考代码（迭代版，性能最优） #

class Solution
{
    public:
    int isPalindrome(string S)
    {
        int left = 0, right = S.size() - 1;
        while (left < right) {
            if (S[left] != S[right]) {
                return 0;
            }
            left++;
            right--;
        }
        return 1;
    }
};

保留递归逻辑的最小修改版本 #

class Solution
{
    public:
    // 仅修改入参为常量引用，消除字符串拷贝开销
    int helper(const string& s, int start, int end){
        if(start >= end) return 1;
        if(s[start] != s[end]) return 0;
        return helper(s, start + 1, end - 1);  
    }
    
    int isPalindrome(string S)
    {
        return helper(S, 0, S.size() - 1);
    }
};

内容的提问来源于stack exchange，提问作者Rahul Kaushik