问题是: 给定n个字符串si,找出最短的字符串S,使得每个si都是S中的子串。 当有多个可能的答案时,输出应该是字典顺序最小的一个。
例如:测试用例:{qgw, qsopd, qwrw, wckumn} 答案应该是“qgwckumnqsopdqwrw”,但我的代码输出“qgwqsopdqwrwckumn”。 我认为问题出在解决函数中,它没有考虑所有可能的上一个字符串。 请帮我看看我应该修改哪里的代码,非常感谢!
下面是我的代码:
class Solution {
vector<vector<string>> req;
string merge(string &a, string &b)
{
int n=a.size(), m=b.size(), len=1, idx=0;
while(len<=min(n, m))
{ if(a!=""&&b!=""){
if(a!=b&&b.find(a)!= string::npos)
{ a="";
}
else if(a.substr(n-len)==b.substr(0, len))
{
idx=len;
}
}
len++;
}
string res=b.substr(idx); // idx is distance to non-overlap and res is the non-overlap str
return res;
}
string solve(vector<string> &words, int prev, int mask, int n, vector<vector<string>> &dp)
//prev:parent word, mask:track which word has been selected
{
if(dp[prev][mask]!="") return dp[prev][mask];// check if the dp is empty
string res="";
int minLen=INT_MAX;
for(int i=0; i<n; i++)
{
if(mask&(1<<i)) continue; //check if the i th word has been used
string temp=req[prev][i]+solve(words, i, mask|(1<<i), n, dp);
int temp_size=temp.size();
if(temp_size<minLen)
{
minLen=temp.size();
res=temp;
}
}
return dp[prev][mask]=res;
}
public:
string shortestSuperstring(vector<string>& words)
{
int n=words.size();
sort(words.begin(), words.end());
req.resize(n, vector<string> (n, ""));
vector<vector<string>> dp(n, vector<string> ((1<<(n+1)), ""));
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(i==j) continue;
req[i][j]=merge(words[i], words[j]);
}
}
string ans="";
int minLen=INT_MAX;
int mask=0;
for(int i=0; i<n; i++)
{
string temp=words[i]+solve(words, i, mask|(1<<i), n, dp);
cout<<"temp: "<<temp<<"\n";
int temp_size=temp.size();
if(temp_size<minLen)
{
minLen=temp.size();
ans=temp;
}
}
return ans;
}
};
现有代码中的主要问题是,当存在多种可能性时,它没有考虑字典顺序最小的要求。它只考虑字符串长度。
您可以对代码进行一些修改来解决此问题:
merge
函数以返回一对整数:
重叠部分的长度和第二个字符串的索引。
这将使您能够跟踪词典顺序。solve
函数中,将 temp_size
与 minLen
进行比较时,
当长度相等时还要考虑字典顺序。
您可以通过在 if 中添加辅助条件来实现此目的
像这样的声明:if(temp_size < minLen || (temp_size == minLen && temp < res))
{
minLen = temp_size;
res = temp;
}
shortestSuperstring
函数中,类似地添加辅助函数
考虑字典顺序的条件:if(temp_size < minLen || (temp_size == minLen && temp < ans))
{
minLen = temp_size;
ans = temp;
}