Algorithms for Coding Interviews in Python/

...

/

Solution: Longest Common Substring

Solution: Longest Common Substring

This review provides a detailed analysis of the different ways to solve the longest common substring problem.

We'll cover the following...

Solution 1: brute force

Press + to interact
def longest_common_substr_length_recursive(s1, s2, i1, i2, count):
    """
    Finds a longest common substring length
    :param lookup_table: Lookup Table
    :param s1: First string
    :param s2: Second string
    :return: Length of longest common substring
    """
    if (i1 == len(s1) or i2 == len(s2)):
      return count
    if s1[i1] == s2[i2]:
      count = longest_common_substr_length_recursive(s1, s2, i1 + 1, i2 + 1, count + 1);
    c1 = longest_common_substr_length_recursive(s1, s2, i1, i2 + 1, 0);
    c2 = longest_common_substr_length_recursive(s1, s2, i1 + 1, i2, 0);
    return max(count, max(c1, c2))
def longest_common_substr_length(s1, s2): 
    return longest_common_substr_length_recursive(s1, s2, 0, 0, 0)
# Driver code to test the above function
if __name__ == '__main__':
    S1 = "0abc321"
    S2 = "123abcdef"
    print(longest_common_substr_length(S1, S2))
    #S1 = "www.educative.io/explore"
    #S2 = "educative.io/edpresso"
    #print(longest_common_substr_length(S1, S2))

Explanation

This is a naive solution which finds all the substrings of the two given strings and then discovers the longest common substrings between the two.

If the strings have a matching character, we recursively check for the remaining length of each and keep a track of the current matching length.

If the characters don’t match, we start two new recursive calls by skipping those characters from each string.

The length of the longest common substring will be the maximum number returned by the three recursive calls .

Time complexity

The time complexity of the above code is O(2n+m)O(2^{n+m}).

The space complexity is O(m+n)O(m+n) ...

Access this course and 1400+ top-rated courses and projects.