Search⌘ K
Home
Courses
Algorithms for Coding Interviews in Python

Solution: Strings Interleaving

Let's analyze the different ways to solve the string interleaving problem.

We'll cover the following...

Solution 1: brute force

Python 3.5
def find_strings_interleaving_recursive(m, n, p, m_index, n_index, p_index):
    """
    Find the interleaving strings
    :param m: String 1
    :param n: String 2
    :param p: String 3
    :param m_index: String 1 index
    :param n_index: String 2 index
    :param p_index: String 3 index
    :return: True if the strings are interleaving, otherwise False
    """
    # if we have reached the end of the all the strings
    if m_index == len(m) and n_index == len(n) and p_index == len(p):
        return True
    # if we have reached the end of 'p' but 'm' or 'n' still has some characters left
    if p_index == len(p):
        return False
    b1 = False
    b2 = False
    if m_index < len(m) and m[m_index] == p[p_index]:
        b1 = find_strings_interleaving_recursive(m, n, p, m_index + 1, n_index, p_index + 1)
    if n_index < len(n) and n[n_index] == p[p_index]:
        b2 = find_strings_interleaving_recursive(m, n, p, m_index, n_index + 1, p_index + 1)
    return b1 or b2
def find_strings_interleaving(m, n, p):
    """
    Find the interleaving strings
    :param m: String 1
    :param n: String 2
    :param p: String 3
    :return: True if the strings are interleaving, otherwise False
    """
    return find_strings_interleaving_recursive(m, n, p, 0, 0, 0)
# Driver code to test the above function
if __name__ == '__main__':
    print(find_strings_interleaving("abd", "cef", "adcbef"))
    print(find_strings_interleaving("abc", "def", "abdccf"))
    print(find_strings_interleaving("abcdef", "mnop", "mnaobcdepf"))

Explanation

The problem follows the longest common subsequence pattern.

A basic brute force solution is to try matching m and n with p one letter at a time. Let’s assume m_index, n_index, and p_index represent the current indexes of m, n, and p strings respectively. Therefore, we have two options at any step:

  • If the letter at ‘m_index’ matches the letter at ‘p_index’, we can recursively match for the remaining lengths of ‘m’ and ‘p’
  • If the letter at ‘n_index’ matches the letter at ‘p_index’, we can recursively match for the remaining lengths of ‘n’ and ‘p’

Time complexity

The time complexity of the above algorithm is exponential ...