1754.构造字典序最大的合并字符串

【LetMeFly】1754.构造字典序最大的合并字符串

力扣题目链接:https://leetcode.cn/problems/largest-merge-of-two-strings/

给你两个字符串 word1word2 。你需要按下述方式构造一个新字符串 merge :如果 word1word2 非空,选择 下面选项之一 继续操作:

  • 如果 word1 非空,将 word1 中的第一个字符附加到 merge 的末尾,并将其从 word1 中移除。
    <ul>
    	<li>例如,<code>word1 = "abc" </code>且 <code>merge = "dv"</code> ,在执行此选项操作之后,<code>word1 = "bc"</code> ,同时 <code>merge = "dva"</code> 。</li>
    </ul>
    </li>
    <li>如果 <code>word2</code> 非空,将 <code>word2</code> 中的第一个字符附加到 <code>merge</code> 的末尾,并将其从 <code>word2</code> 中移除。
    <ul>
    	<li>例如,<code>word2 = "abc" </code>且 <code>merge = ""</code> ,在执行此选项操作之后,<code>word2 = "bc"</code> ,同时 <code>merge = "a"</code> 。</li>
    </ul>
    </li>
    
    TEXT

返回你可以构造的字典序 最大 的合并字符串 merge

长度相同的两个字符串 ab 比较字典序大小,如果在 ab 出现不同的第一个位置,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 的末尾。
TEXT

示例 2:

输入:word1 = "abcabc", word2 = "abdcaba"
输出:"abdcabcabcaba"
TEXT

 

提示:

  • 1 <= word1.length, word2.length <= 3000
  • word1word2 仅由小写英文组成

方法一:贪心

我们不断比较两个字符串word1word2哪个字典序大,每次把字典序大的字符串,取一个字母添加到merge

例如cadbac

1
2
3
word1:  cad
word2: bac
merge:
AVRASM

cad>bac

1
2
3
word1:  ad
word2: bac
merge: c
AVRASM

ad<bac

1
2
3
word1:  ad
word2: ac
merge: cb
AVRASM

这时候word1word2的首字母都是a,但是word1的第二个字母d小于word2的第二个字母c,因此选择word2

1
2
3
word1:  ad
word2: c
merge: cba
AVRASM

ad<c

1
2
3
word1:  ad
word2:
merge: cbac
AVRASM

此时word2为空,将word1添加到merge中即可

1
2
3
word1:
word2:
merge: cbacad
AVRASM
  • 时间复杂度O(len(word1)×len(word2))
  • 空间复杂度O(len(word1)+len(word2))

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
string largestMerge(string word1, string word2) {
string ans;
while (word1.size() && word2.size()) {
if (word1 > word2) {
ans += word1[0];
word1 = word1.substr(1);
}
else {
ans += word2[0];
word2 = word2.substr(1);
}
}
if (word1.size())
ans += word1;
if (word2.size())
ans += word2;
return ans;
}
};
CPP

同步发文于CSDN,原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/128426600


1754.构造字典序最大的合并字符串
https://blog.letmefly.xyz/2022/12/24/LeetCode 1754.构造字典序最大的合并字符串/
作者
发布于
2022年12月24日
许可协议