class Solution {
public:
string largestMerge(string word1, string word2) {
}
};
1754. 构造字典序最大的合并字符串
给你两个字符串 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 之后。
示例 1：
输入：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 的末尾。
示例 2：
输入：word1 = "abcabc", word2 = "abdcaba" 输出："abdcabcabcaba"
提示：
1 <= word1.length, word2.length <= 3000word1 和 word2 仅由小写英文组成原站题解
java 解法, 执行用时: 49 ms, 内存消耗: 42.6 MB, 提交时间: 2022-12-24 12:03:48
class Solution {
public String largestMerge(String word1, String word2) {
int m = word1.length(), n = word2.length();
String str = word1 + "@" + word2 + "*";
int[] suffixArray = buildSuffixArray(str);
int[] rank = new int[m + n + 2];
for (int i = 0; i < m + n + 2; i++) {
rank[suffixArray[i]] = i;
}
StringBuilder merge = new StringBuilder();
int i = 0, j = 0;
while (i < m || j < n) {
if (i < m && rank[i] > rank[m + 1 + j]) {
merge.append(word1.charAt(i));
i++;
} else {
merge.append(word2.charAt(j));
j++;
}
}
return merge.toString();
}
public int[] buildSuffixArray(String text) {
int[] order = sortCharacters(text);
int[] classfiy = computeCharClasses(text, order);
int len = 1;
int n = text.length();
for (int i = 1; i < n; i <<= 1) {
order = sortDoubled(text, i, order, classfiy);
classfiy = updateClasses(order, classfiy, i);
}
return order;
}
public int[] sortCharacters(String text) {
int n = text.length();
int[] count = new int[128];
int[] order = new int[n];
for (int i = 0; i < n; i++) {
char c = text.charAt(i);
count[c]++;
}
for (int i = 1; i < 128; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
count[text.charAt(i)]--;
order[count[text.charAt(i)]] = i;
}
return order;
}
public int[] computeCharClasses(String text, int[] order) {
int n = text.length();
int[] res = new int[n];
res[order[0]] = 0;
for (int i = 1; i < n; i++) {
if (text.charAt(order[i]) != text.charAt(order[i - 1])) {
res[order[i]] = res[order[i - 1]] + 1;
} else {
res[order[i]] = res[order[i - 1]];
}
}
return res;
}
public int[] sortDoubled(String text, int len, int[] order, int[] classfiy) {
int n = text.length();
int[] count = new int[n];
int[] newOrder = new int[n];
for (int i = 0; i < n; i++) {
count[classfiy[i]]++;
}
for (int i = 1; i < n; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
int start = (order[i] - len + n) % n;
int cl = classfiy[start];
count[cl]--;
newOrder[count[cl]] = start;
}
return newOrder;
}
public int[] updateClasses(int[] newOrder, int[] classfiy, int len) {
int n = newOrder.length;
int[] newClassfiy = new int[n];
newClassfiy[newOrder[0]] = 0;
for (int i = 1; i < n; i++) {
int curr = newOrder[i];
int prev = newOrder[i - 1];
int mid = curr + len;
int midPrev = (prev + len) % n;
if (classfiy[curr] != classfiy[prev] || classfiy[mid] != classfiy[midPrev]) {
newClassfiy[curr] = newClassfiy[prev] + 1;
} else {
newClassfiy[curr] = newClassfiy[prev];
}
}
return newClassfiy;
}
}
java 解法, 执行用时: 55 ms, 内存消耗: 42.1 MB, 提交时间: 2022-12-24 12:02:59
class Solution {
public String largestMerge(String word1, String word2) {
StringBuilder merge = new StringBuilder();
int i = 0, j = 0;
while (i < word1.length() || j < word2.length()) {
if (i < word1.length() && word1.substring(i).compareTo(word2.substring(j)) > 0) {
merge.append(word1.charAt(i));
i++;
} else {
merge.append(word2.charAt(j));
j++;
}
}
return merge.toString();
}
}
javascript 解法, 执行用时: 76 ms, 内存消耗: 47 MB, 提交时间: 2022-12-24 12:02:42
/**
* @param {string} word1
* @param {string} word2
* @return {string}
*/
var largestMerge = function(word1, word2) {
let merge = '';
let i = 0, j = 0;
while (i < word1.length || j < word2.length) {
if (i < word1.length && word1.slice(i) > word2.slice(j)) {
merge += word1[i];
i++;
} else {
merge += word2[j];
j++;
}
}
return merge;
};
golang 解法, 执行用时: 0 ms, 内存消耗: 6.1 MB, 提交时间: 2022-12-24 12:02:31
func largestMerge(word1, word2 string) string {
merge := []byte{}
i, j, n, m := 0, 0, len(word1), len(word2)
for i < n || j < m {
if i < n && word1[i:] > word2[j:] {
merge = append(merge, word1[i])
i += 1
} else {
merge = append(merge, word2[j])
j += 1
}
}
return string(merge)
}
python3 解法, 执行用时: 88 ms, 内存消耗: 15.2 MB, 提交时间: 2022-12-24 12:02:15
class Solution:
def largestMerge(self, word1: str, word2: str) -> str:
merge = []
i, j, n, m = 0, 0, len(word1), len(word2)
while i < n or j < m:
if i < n and word1[i:] > word2[j:]:
merge.append(word1[i])
i += 1
else:
merge.append(word2[j])
j += 1
return ''.join(merge)