Teaching Kids Programming – Longest Common Prefix Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of lowercase alphabet strings words, return the longest common prefix.

Example 1
Input
words = [“anthony”, “ant”, “antigravity”]
Output
“ant”
Explanation
“ant” is the longest common prefix between the three strings.

Hint:
We can iterate one letter at a time for each word and check that they must all be equal. Move up until we cant.

Algorithm to Compute the Longest Common Prefix String

First we need to compute the minimum length of all the strings in the list. This takes O(N) where N is the number of strings. Let’s say min length is K. Then we need to check K letters and see if each word has the same character at position i where i is from [0, k).

1
2
3
4
5
6
7
8
9
10
class Solution:
    def longestCommonPrefix(self, words):
        i = 0
        min_len = min(len(w) for w in words) 
        while i < min_len:
            col_chars = set({w[i] for w in words})
            if len(col_chars) != 1:
                break
            i += 1
        return words[0][:i]
class Solution:
    def longestCommonPrefix(self, words):
        i = 0
        min_len = min(len(w) for w in words) 
        while i < min_len:
            col_chars = set({w[i] for w in words})
            if len(col_chars) != 1:
                break
            i += 1
        return words[0][:i]

We then last return any string’s common prefix [:i] where i is the furthest index that all the strings share the prefix characters. The time compleixty is O(N+K*N) and the space complexity is O(N) as we need a set determine if there is only one character at prefix index i.

See also: Bruteforce and Rolling Hash Algorithm to Compute the Longest Happy Prefix String (Equal Prefix and Suffix)

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
395 words
Last Post: GoLang: Algorithm to Compute the Range Sum of a Binary Search Tree
Next Post: GoLang Function to Check if a String is a Subsequence of Another

The Permanent URL is: Teaching Kids Programming – Longest Common Prefix Algorithm

Leave a Reply