【Leetcode】1754. Largest Merge Of Two Strings

题目地址：

https://leetcode.com/problems/largest-merge-of-two-strings/

给定两个字符串$s_1$和$s_2$，从一个空串$s$开始，开两个指针$i=j=0$，每一步可以将$s_1[i]$或$s_2[j]$添到$s$后面，同时$i$或$j$向后挪动一位。问最后得到的最大字典序的$s$是什么。

如果$s_1[i]>s_2[j]$，那么显然应该添$s_1[i]$；反之如果$s_1[i]<s_2[j]$，那么显然应该添$s_2[j]$。一般地，如果$s_1[i]>s_2[j]$，那么就应该添$s_1[i]$，反之类似。粗略的原因是这样的，如果$s_1[i:i_1-1]=s_2[j:j_1-1]$，但是$s_1[i_1]>s_2[j_1]$，先添$s_1[i]$可以使$s_1[i_1]$优先出现在将要添的字符选项里。严格证明可以用反证法。如果此法不优，则按照更优的方法添加字符，当添加到$s_2[j_1]$的时候，将更优的方法做一个对称变换（即添$s_1$的时候变为添$s_2$，反之亦然），那么此时就是添$s_1[i_1]$了，显然字典序更大。代码如下：

class Solution {
 public:
  string largestMerge(string s1, string s2) {
    string s;
    for (int i = 0, j = 0; i < s1.size() || j < s2.size();)
	  s += bigger(s1, s2, i, j) ? s1[i++] : s2[j++];

    return s;
  }

  bool bigger(string& s1, string& s2, int i, int j) {
    while (i < s1.size() && j < s2.size()) {
      if (s1[i] > s2[j]) return true;
      else if (s1[i] < s2[j]) return false;
      else i++, j++;
    }

    return j == s2.size();
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时间复杂度 O ( min ⁡ { l s 1 , l s 2 } ( l s 1 + l s 2 ) ) O(\min\{l_{s_1},l_{s_2}\}(l_{s_1}+l_{s_2})) O(min{ls1​​,ls2​​}(ls1​​+ls2​​))，空间$O(1)$。