Skip to content

1754. Largest Merge Of Two Strings 👍

  • Time: $O(|\texttt{word1}|^2 + |\texttt{word2}|^2)$
  • Space: $O(|\texttt{word1}|^2 + |\texttt{word2}|^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
 public:
  string largestMerge(string word1, string word2) {
    if (word1.empty())
      return word2;
    if (word2.empty())
      return word1;
    return word1 > word2 ? word1[0] + largestMerge(word1.substr(1), word2)
                         : word2[0] + largestMerge(word1, word2.substr(1));
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
  public String largestMerge(String word1, String word2) {
    if (word1.isEmpty())
      return word2;
    if (word2.isEmpty())
      return word1;
    return word1.compareTo(word2) > 0 ? word1.charAt(0) + largestMerge(word1.substring(1), word2)
                                      : word2.charAt(0) + largestMerge(word1, word2.substring(1));
  }
}

1
2
3
4
5
6
7
8
9
class Solution:
  def largestMerge(self, word1: str, word2: str) -> str:
    if not word1:
      return word2
    if not word2:
      return word1
    if word1 > word2:
      return word1[0] + self.largestMerge(word1[1:], word2)
    return word2[0] + self.largestMerge(word1, word2[1:])