[toc]
Company tags: Google, Microsoft, Amazon, Apple, Adobe, Bloomberg, e-Bay, Facebook
Problem Statement
Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “”.
Constraints:
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i]
consists of only lower-case English letters.
Examples
Letโs have a look at some examples to improve our understanding of this problem.
Example 1: Input: strs = [“flower”, “flow”, “flight”] Output: “fl” Explanation: The common prefix is “fl” Example 2: Input: strs = [“dog”, “racecar”, “car”] Output: ” “ Explanation: There is no common prefix among the input strings. Example 3: Input: strs = [“aabc”, “aabab”, “aab”, “aabbaabb”] Output: “aab” Explanation: The common prefix is “aab” Example 4: Input: strs = [“apple”, “aPP”] Output: “a” Explanation: Upper-case letters are not considered. Example 5: Input: strs = [“finxter”] Output: “finxter” Explanation: There is only one input string. |
Now letโs dive into various methods to solve the problem.
Method 1: Brute Force Approach
Approach: The naรฏve approach would be to check for each string and compare the characters in each string to find the common prefix.
Algorithm:
- Initialize the first string to the โ
curr
โ variable. - If the list is empty, return an empty string.
- If the list contains only one string, return that string.
- For every other string in the list- Compare the character of the string with the character in the โcurrโ variable.
- If the characters are equal, continue comparing, else break the loop.
- Update the โ
curr
โ variable with the matched substring.
Solution:
def common_prefix(strs): curr = strs[0] if not strs: return " " if len(strs) == 1: return curr for i in range(1, len(strs)): if len(curr) == 0: break temp = '' for j in range(len(strs[i])): if j < len(curr) and curr[j] == strs[i][j]: temp = temp + curr[j] else: break curr = temp return curr
Test Case Analysis:
# Example 1 strs = [“flower”, “flow”, “flight”] print(common_prefix(strs)) # fl # Example 2 strs = [“dog”, “racecar”, “car”] print(common_prefix(strs)) # # Example 3 strs = [“aabc”, “aabab”, “aab”, “aabbaabb”] print(common_prefix(strs)) # aab # Example 4 strs = [“apple”, “aPP”] print(common_prefix(strs)) # a # Example 5 strs = [“finxter”] print(common_prefix(strs)) # finxter |
Yeah! It passed all the test cases.
Complexity Analysis:
- Time Complexity: The time complexity of this method is O(n * k), where n is the size of the array and k is the size of the longest string.
- Space Complexity: O(1) as no extra space was used here.
Method 2: Using The Two Pointer Approach
Approach: In this approach, you must sort the list of strings in lexicographical order (a to z). Then, compare the first string with the last string, character by character to find the longest common prefix.
The following illustration will help you to understand the working principle behind this approach:
In the above examplethe given array is [Flower, Flow, Flight]
. After sorting it with the help of sort() method in Python it stores the strings in the folowing order: [Fligth, Flow, Flower]
. Once the string has been sorted, every element/character of the first and last strings of the sorted array are compared. When a match is found it is stored in a variable (temp
). As soon as the match is not found, the loop breaks and the value stored in the temp
variable is returned as the output.
Algorithm:
- Sort the given list of strings.
- If the list is empty, return an empty string.
- If the list contains only one string, return that string.
- Store the first and last strings in variables โ
first
โ and โlast
,” respectively. Also intialize a “temp
” variable that will store the output. - Compare each character of the two strings one by one.
- If equal, add them to a temporary variable, else
break
out of the loop. - Finally return the temp.
Solution:
def common_prefix(strs): strs.sort() if not strs: return " " if len(strs) == 1: return strs[0] first = strs[0] last = strs[-1] temp = "" for i in range(len(first)): if first[i] == last[i]: temp = temp + first[i] else: break return temp
Test case Analysis:
# Example 1 strs = [“flower”, “flow”, “flight”] print(common_prefix(strs)) # fl # Example 2 strs = [“dog”, “racecar”, “car”] print(common_prefix(strs)) # # Example 3 strs = [“aabc”, “aabab”, “aab”, “aabbaabb”] print(common_prefix(strs)) # aab # Example 4 strs = [“apple”, “aPP”] print(common_prefix(strs)) # a # Example 5 strs = [“finxter”] print(common_prefix(strs)) # finxter |
Yeah! It passed all the test cases.
Complexity Analysis: The time complexity of this method is O(k* n* log n), where n
is the size of the array, k
is the size of the longest string, and log(n) is the time taken to sort the array.
Optimal Solution: Divide and Conquer Using zip And set
Approach: This is the most Pythonic way/approach to solve the given problem. The idea here is to divide the prefix characters of the given strings into sets of tuples and then extract the longest common prefix accordingly. Let’s have a look at the following diagram to understand this concept:
Recap to zip() Method in Python: The zip()
function takes an arbitrary number of iterables and aggregates them to a single iterable, a zip object. It combines the i-th values of each iterable argument into a tuple. Hence, if you pass two iterables, each tuple will contain two values. If you pass three iterables, each tuple will contain three values. For example, zip together lists [1, 2, 3]
and [4, 5, 6]
to [(1,4), (2,5), (3,6)]
.
Read more about the zip() method here!
Algorithm:
- If the list is empty, return an empty string.
- If the list contains only one string, return that string.
- Initialize a
temp
variable that will store an empty string at the start. - Upon every string in the tuples generated by the
zip()
method, use theset()
function. - Check the length of the set. If it is greater than 1, break the loop.
- Else, update the
temp
to the next character. - Return
temp
.
Solution:
def common_prefix(strs): if not strs: return " " if len(strs) == 1: return strs[0] temp = '' for chr in zip(*strs): if len(set(chr)) > 1: break else: temp = temp + chr[0] return temp
Test Case Analysis:
# Example 1 strs = [“flower”, “flow”, “flight”] print(common_prefix(strs)) # fl # Example 2 strs = [“dog”, “racecar”, “car”] print(common_prefix(strs)) # # Example 3 strs = [“aabc”, “aabab”, “aab”, “aabbaabb”] print(common_prefix(strs)) # aab # Example 4 strs = [“apple”, “aPP”] print(common_prefix(strs)) # a # Example 5 strs = [“finxter”] print(common_prefix(strs)) # finxter |
Yeah! It passed all the test cases.
Complexity Analysis: The time complexity of this method is O(min(k) * n), where n
is the size of the array and k
is the size of the shortest string.
Conclusion
I hope you enjoyed this coding interview question. Please stay tuned and subscribe for more interesting coding problems.
Post Credits: Shubham Sayon and Rashi Agarwal
Recommended: Finxter Computer Science Academy
- One of the most sought-after skills on Fiverr and Upwork is web scraping. Make no mistake: extracting data programmatically from websites is a critical life skill in todayโs world thatโs shaped by the web and remote work.
- So, do you want to master the art of web scraping using Pythonโs BeautifulSoup?
- If the answer is yes โ this course will take you from beginner to expert in Web Scraping.