[Google Interview] How To Find The Longest Common Prefix?


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. 1 <= strs.length <= 200
  2. 0 <= strs[i].length <= 200
  3. 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:

  1. Initialize the first string to the “curr” variable.
  2. If the list is empty, return an empty string.
  3. If the list contains only one string, return that string.
  4. For every other string in the list- Compare the character of the string with the character in the “curr” variable.
  5. If the characters are equal, continue comparing, else break the loop.
  6. 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 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:

  1. Sort the given list of strings.
  2. If the list is empty, return an empty string.
  3. If the list contains only one string, return that string.
  4. Store the first and last strings in variables “first” and “last,” respectively. Also intialize a “temp” variable that will store the output.
  5. Compare each character of the two strings one by one.
  6. If equal, add them to a temporary variable, else break out of the loop.
  7. 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* 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:

  1. If the list is empty, return an empty string.
  2. If the list contains only one string, return that string.
  3. Initialize a temp variable that will store an empty string at the start.
  4. For every tuple in the zip of strings, use the set function.
  5. Check the length of the set. If it is greater than 1, break the loop.
  6. Else, update the temp to the next character.
  7. 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

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.



Source link

Latest articles

Related articles

Leave a reply

Please enter your comment!
Please enter your name here