给定一个字符串列表,你可以将这些字符串连接成一个循环字符串,对于每个字符串,你可以选择是否翻转它。
在所有可能的循环字符串中,你需要分割循环字符串(这将使循环字符串变成一个常规的字符串),然后找到字典序最大的字符串。
具体来说,要找到字典序最大的字符串,你需要经历两个阶段:
你的工作是在所有可能的常规字符串中找到字典序最大的一个。
示例:
输入: "abc", "xyz"
输出: "zyxcba"
解释: 你可以得到循环字符串 "-abcxyz-", "-abczyx-", "-cbaxyz-", "-cbazyx-",
其中 '-' 代表循环状态。
答案字符串来自第四个循环字符串,
你可以从中间字符 'a' 分割开然后得到 "zyxcba"。
注意:
输入字符串只包含小写字母。
所有字符串的总长度不会超过 1,000。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/split-concatenated-strings 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
string splitLoopedString(vector<string>& strs) {
string rev, all;
for(string& s : strs)
{
rev = s;
reverse(rev.begin(), rev.end());
if(rev > s)//反转后的更大
s = rev;
}
string ans, temp;
for(int i = 0, j, k; i < strs.size(); ++i)
{ //从字符串 i 切开
temp = "";
for(j = i+1; j < strs.size(); ++j)
temp += strs[j];//前部分是后面的 i+1, n-1
for(j = 0; j < i; ++j)
temp += strs[j];//接着是前面的 0, i-1
for(j = 0; j <= strs[i].size(); ++j)
{
rev = strs[i].substr(j)+temp+strs[i].substr(0,j);
ans = max(ans, rev);
}
reverse(strs[i].begin(), strs[i].end());//还要考虑反转后的情况
for(j = 0; j <= strs[i].size(); ++j)
{
rev = strs[i].substr(j)+temp+strs[i].substr(0,j);
ans = max(ans, rev);
}
reverse(strs[i].begin(), strs[i].end());//反转回去
}
return ans;
}
};
184 ms 200.7 MB