Merge Two Sorted Strings Lexicographically

In this lesson, we will learn how to merge two strings lexicographically.

We'll cover the following

What does “Merging Two Sorted Strings Lexicographically” Mean?

Lexicographical means according to the alphabetical order.

Lower case letters are different from upper case letters, therefore, they are treated differently. Also, all upper case letters come before all lower case letters. Alphabetic sorting is as follows: A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, a, b, c, d, e, f, g, h, i, j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,zj, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z

Merging strings lexicographically.
Merging strings lexicographically.

Implementation

Press + to interact
def merge(string1, string2) :
  # Base Case1
  if string1 == "" :
    if string2 == "" : 
      return ""
    return string2
  # Base Case2
  elif string2 == "" :
    return string1
  # Recursive Case1
  elif string1[0] > string2[0] :
      return string2[0] + merge(string1, string2[1:])
  # Recursive Case2
  return string1[0] + merge(string1[1:], string2)
# Driver Code
string1 = "acu"
string2 = "bst"
print(merge(string1, string2))

Explanation

The two strings passed, in this case, string1 and string2 to the function merge() are sorted. The characters in the two strings may satisfy 11 of the 55 conditions:

  1. Both string1 and string2 are equal to an empty string "".

    • In this case return "".

  2. string1 == "" therefore, return string2.

  3. string2 == "" therefore, return string1.

These 33 conditions will be the base case. Here no string manipulation is occurring. We just return the specific string.

  1. The first element of string1 is greater than the first element of string2.

    In Python, an alphabet can be compared with another alphabet. This means that a < b, b < c, c < d and so on.

    • In this case, save the first element of string2 since it is smaller. Then recursively call another instance of merge() with that element removed.

  2. The first element of string1 is less than the first element of string2.

    • In this case, save the first element of string1 since it is smaller. Then recursively call another instance of merge() with that element removed.

Let’s have a look at an illustration:

In the next lesson, we have a challenge for you to solve.