Longest Common Prefix — Solving with 10+ Methods using Python

Question (LeetCode #14):

Write the function to find the longest common prefix string among an array of words. Note: all input words are in lower case letters (hence upper/lower-case conversion is not required)

Solutions:

• #1) Use built-inall() and startswith() functions. It first finds the shortest word in the input array, then it iterates each character of the shortest word to find out whether the character is common to the rest of words.
  O(S) time where S is the total number of characters for all words in the array, O(1) space;

• #2) Use enumerate() and nested for loop to check each char for each word. O(S) time where S is the total number of characters for all words in the array, O(1) space;

• #3) Use zip() andset(), if the length of set greater than 1, return the current longest common prefix. enumerate(zip(*strs)) returns index and tuple of characters from each word. To note here set() to convert the list to set has time complexity of O(N) where N is the number of words in the array. Consider the for loop, overall time complexity is still O(S) where S is the total number of characters for all words in the array, O(1) space;

• #4) Use zip() andset() without enumerate(), zip(*str) returns a zip object where each tuple has characters with the corresponding index from each word. Similarly, O(S) time where S is the total number of characters for all words in the array, O(1) space;

• #5) Use min() and max() on array of strings. These two functions return the first and last words of the sorted input array (lexicographically). If the character in min_s is in max_s at the corresponding index, the character must be in the remaining words at the corresponding index as well. This is because the input array of words have already been sorted;

• #6) Use sorted() on the array of strings and compare first and last words of sorted array index by index. It is the variant of #5;

• #7) Use find(), start with the first word in the input array as the longest prefix. Horizontal scanning where the outer loop is for each individual remaining words, inner loop for each individual character of the word, decrement the length of the longest prefix. O(S) time where S is the total number of characters for all words in the array, O(1) space;

• #8) Vertical scanning where the outer loop is for each character of the first word in the input array, inner loop for each individual words. Increment the index of the first word as the longest common prefix. It is more optimized compared to #7 in dealing with the case where there is a very short word at end of the input array. O(S) time where S is the total number of characters for all words in the array, O(1) space;

• #9) Divide and conquer, the intuition is LCP(W1,W2,W3...Wn) = LCP(LCP(W1,W2...Wk-1),LCP(Wk,Wk+1...Wn)) Hence we can recursively divide the problem of finding LCP of an input array of words into 2 sub-problems of finding LCP on sub-components. commonPrefix() returns the common prefix of two sub-components. We recursively divide and combine from a basic case to make up the final longest common prefix. O(S) time where S is the total number of characters for all words in the array, O(Mlog(N)) space where N is the number of words in the array, M is the largest length of a word as we make log(N) recursive call and each call requires O(M) space;

• #10) Binary search on the length of the prefix on the first word of the input array. isCommonPrefix() function test whether a given length of the first word produces a common prefix for all words in the array. O(Slog(M)) time where S is the total number of characters for all words in the array, M is the length of the longest word in the array as we iterate log(M) times for the binary search on prefix length. For each time, we perform comparisons on N words of maximum M characters. Hence O(MNlog(M)) = O(Slog(M)) time, O(1) space;

With all the efforts above, interestingly, Python has a built-in commonprefix()function to solve the problem in single-line:

return os.path.commonprefix(strs)