字符串通过引用传递工作良好，否则在LCS问题中不存在

Question

如果我在函数方法中传递字符串引用，那么它工作得很好，但是如果我没有通过引用传递它，那么测试用例就会失败，超过了时间限制。谁能告诉我我错过了什么?

工作代码:

class Solution {
public:
int lcsUtil(string& s1,int ind1,string& s2,int ind2,vector< vector<int>>&dp){
if(ind1<0 || ind2<0) return 0;

if(dp[ind1][ind2] != -1) return dp[ind1][ind2];

if(s1[ind1] == s2[ind2])
return dp[ind1][ind2] = 1 + lcsUtil(s1,ind1-1,s2,ind2-1,dp);

else 
return dp[ind1][ind2] = 0 + max(lcsUtil(s1,ind1-1,s2,ind2,dp),lcsUtil(s1,ind1,s2,ind2-1,dp));
}
int longestCommonSubsequence(string text1, string text2) {
vector< vector<int> > dp (text1.size(),vector<int>(text2.size(),-1));
return lcsUtil(text1,text1.size()-1,text2,text2.size()-1,dp);
}
};

不工作代码:

class Solution {
public:
int lcsUtil(string s1,int ind1,string s2,int ind2,vector< vector<int>>&dp){
if(ind1<0 || ind2<0) return 0;

if(dp[ind1][ind2] != -1) return dp[ind1][ind2];

if(s1[ind1] == s2[ind2])
return dp[ind1][ind2] = 1 + lcsUtil(s1,ind1-1,s2,ind2-1,dp);

else 
return dp[ind1][ind2] = 0 + max(lcsUtil(s1,ind1-1,s2,ind2,dp),lcsUtil(s1,ind1,s2,ind2-1,dp));
}
int longestCommonSubsequence(string text1, string text2) {
vector< vector<int> > dp (text1.size(),vector<int>(text2.size(),-1));
return lcsUtil(text1,text1.size()-1,text2,text2.size()-1,dp);
}
};

问题语句

https://leetcode.com/problems/longest-common-subsequence/

Answer 1

按值传递std::strings时，就像在第二个示例中所做的那样，每次都要复制它们。这需要时间(和内存)，并解释了超出限制的原因。您也可能因为超出内存限制而失败。当您通过引用传递它们时，您不会复制字符串。而是引用已经存在的字符串。