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.
–EOF (The Ultimate Computing & Technology Blog) —
loading...
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