题目描述
给你两个字符串 word1
和 word2
。你需要按下述方式构造一个新字符串 merge
:如果 word1
或 word2
非空,选择 下面选项之一 继续操作:
- 如果
word1
非空,将word1
中的第一个字符附加到merge
的末尾,并将其从word1
中移除。- 例如,
word1 = "abc"
且merge = "dv"
,在执行此选项操作之后,word1 = "bc"
,同时merge = "dva"
。
- 例如,
- 如果
word2
非空,将word2
中的第一个字符附加到merge
的末尾,并将其从word2
中移除。- 例如,
word2 = "abc"
且merge = ""
,在执行此选项操作之后,word2 = "bc"
,同时merge = "a"
。
- 例如,
返回你可以构造的字典序 最大 的合并字符串 merge
。
长度相同的两个字符串 a
和 b
比较字典序大小,如果在 a
和 b
出现不同的第一个位置,a
中字符在字母表中的出现顺序位于 b
中相应字符之后,就认为字符串 a
按字典序比字符串 b
更大。例如,"abcd"
按字典序比 "abcc"
更大,因为两个字符串出现不同的第一个位置是第四个字符,而 d
在字母表中的出现顺序位于 c
之后。
样例
输入:word1 = "cabaa", word2 = "bcaaa"
输出:"cbcabaaaaa"
解释:构造字典序最大的合并字符串,可行的一种方法如下所示:
- 从 word1 中取第一个字符:merge = "c",word1 = "abaa",word2 = "bcaaa"
- 从 word2 中取第一个字符:merge = "cb",word1 = "abaa",word2 = "caaa"
- 从 word2 中取第一个字符:merge = "cbc",word1 = "abaa",word2 = "aaa"
- 从 word1 中取第一个字符:merge = "cbca",word1 = "baa",word2 = "aaa"
- 从 word1 中取第一个字符:merge = "cbcab",word1 = "aa",word2 = "aaa"
- 将 word1 和 word2 中剩下的 5 个 a 附加到 merge 的末尾。
输入:word1 = "abcabc", word2 = "abdcaba"
输出:"abdcabcabcaba"
限制
1 <= word1.length, word2.length <= 3000
word1
和word2
仅由小写英文组成。
算法1
(贪心,暴力) $O((n + m) ^ 2)$
- 设 $i$ 和 $j$ 分别从两个字符串的开头开始遍历。
- 如果 $i$ 和 $j$ 都没有到字符串末尾,则比较以 $i$ 和 $j$ 开头的两个后缀的字典序,取二者中最大的后缀,其指针向后移动。
时间复杂度
- 遍历 $O(n + m)$ 次,每一次可能需要 $O(n + m)$ 的时间比较,故总时间复杂度为 $O((n + m) ^ 2)$。
空间复杂度
- 需要 $O(n + m)$ 的额外空间存储答案。
C++ 代码
class Solution {
private:
bool greater(const string &s1, int idx1, const string &s2, int idx2) {
for (int i = idx1, j = idx2; i < s1.size() && j < s2.size(); i++, j++)
if (s1[i] != s2[j])
return s1[i] > s2[j];
return s1.size() - idx1 > s2.size() - idx2;
}
public:
string largestMerge(string word1, string word2) {
const int n = word1.size(), m = word2.size();
string ans;
int i = 0, j = 0;
while (i < n || j < m) {
if (i == n) ans += word2[j++];
else if (j == m) ans += word1[i++];
else {
if (greater(word1, i, word2, j)) ans += word1[i++];
else ans += word2[j++];
}
}
return ans;
}
};
算法2
(贪心,后缀数组) $O((n + m) \log (n + m))$
- 按照算法 1 的贪心思路,通过后缀数组快速求出字符串的排名。
- 具体地,将两个字符串
A
和B
按照A0B
的方式组合在一起,求出其所有后缀的排名,然后拼接时就可以快速判断两个后缀的排名。
时间复杂度
- 后缀数组的时间复杂度为 $O((n + m) \log (n + m))$。
空间复杂度
- 需要 $O(n + m)$ 的额外空间存储后缀数组的数据结构和答案。
C++ 代码
#define N 6010
class Solution {
private:
int cnt[N], sa[N], rk[N], oldrk[N], id[N];
int n;
bool is_equal(int x, int y, int w) {
if (x > y) swap(x, y);
if (oldrk[x] != oldrk[y]) return false;
if (x + w < n && y + w >= n) return false;
if (x + w >= n) return true;
return oldrk[x + w] == oldrk[y + w];
}
public:
string largestMerge(string word1, string word2) {
const int w1 = word1.size(), w2 = word2.size();
n = w1 + 1 + w2;
int m = 300;
for (int i = 0; i < m; i++) cnt[i] = 0;
for (int i = 0; i < n; i++)
if (i < w1) cnt[rk[i] = word1[i]]++;
else if (i == w1) cnt[rk[i] = 0]++;
else cnt[rk[i] = word2[i - w1 - 1]]++;
for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[i]]] = i;
for (int w = 1; w < n; w <<= 1) {
int c = 0;
for (int i = n - w; i < n; i++) id[c++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= w) id[c++] = sa[i] - w;
for (int i = 0; i < m; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[rk[id[i]]]++;
for (int i = 1; i < m; i++) cnt[i] += cnt[i - 1];
for (int i = n - 1; i >= 0; i--) sa[--cnt[rk[id[i]]]] = id[i];
for (int i = 0; i < n; i++) oldrk[i] = rk[i];
m = 0;
rk[sa[0]] = m++;
for (int i = 1; i < n; i++)
rk[sa[i]] = is_equal(sa[i - 1], sa[i], w) ? m-1: m++;
}
string ans;
for (int i = 0, j = w1 + 1, c = 0; c < w1 + w2; c++) {
if (i == w1) ans += word2[j++ - w1 - 1];
else if (j == n) ans += word1[i++];
else {
if (rk[i] > rk[j]) ans += word1[i++];
else ans += word2[j++ - w1 - 1];
}
}
return ans;
}
};