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: Example 3: Example 4: Example 5: |
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 # Example 3 # Example 4 # Example 5 |
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 Sorting
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 # Example 3 # Example 4 # Example 5 |
Yeah! It passed all the test cases.
Complexity Analysis: The time complexity of this method is O(k* n* logn), 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: Using zip And set
Approach: This is the most Pythonic way/approach to solve the given problem.
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.
- For every tuple in the zip of strings, use the set 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 # Example 3 # Example 4 # Example 5 |
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
Please stay tuned and subscribe for more interestin. 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.