Longest Common Prefix

Finding the longest common prefix among an array of strings is a common task. We can approach this problem by comparing characters across all the strings. Here’s a straightforward solution:

  1. If the given list strs is empty or contains an empty string, return an empty string.
  2. Find the shortest string in strs. This will be our limit for checking characters.
  3. Iterate through each character of the shortest string and compare it with the corresponding character in all the other strings.
  4. If any character does not match, return the common prefix found so far.
  5. If all characters match for the length of the shortest string, return the shortest string as the longest common prefix.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs or "" in strs:
            return ""

        # Find the shortest string
        shortest = min(strs, key=len)

        # Iterate through each character in the shortest string
        for i in range(len(shortest)):
            char = shortest[i]
            for string in strs:
                # If any character does not match, return the common prefix found so far
                if string[i] != char:
                    return shortest[:i]

        # Return the shortest string if all characters match
        return shortest

This code returns the correct common prefix for the given examples and satisfies the constraints mentioned.

Identifying Problem Isomorphism

“Longest Common Prefix” has a close resemblance to “Shortest Common Supersequence”.

In the “Longest Common Prefix” problem, you’re given an array of strings, and you are to find the longest common prefix that all these strings share.

Similarly, in the “Shortest Common Supersequence” problem, you’re given two strings, and you are to find the shortest supersequence that contains both these strings. This means you’re looking for the smallest string that has both input strings as subsequences.

The difference is in how the strings are compared. In “Longest Common Prefix”, you’re looking for a string that all input strings begin with, while in the “Shortest Common Supersequence” problem, you’re trying to find a string that contains all the input strings as subsequences.

The “Longest Common Prefix” problem is simpler because it only involves comparing the beginnings of the strings, while “Shortest Common Supersequence” requires finding a string that contains two others, which requires more complex logic.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def longestCommonPrefix(self, v: List[str]) -> str:
        ans=""
        v=sorted(v)
        first=v[0]
        last=v[-1]
        for i in range(min(len(first),len(last))):
            if(first[i]!=last[i]):
                return ans
            ans+=first[i]
        return ans

Problem Classification

This is about the task of finding the longest common prefix among a list of strings. This problem can be classified in the following ways:

  1. String Manipulation: The problem requires operations to be performed on strings, such as checking characters one by one in the strings to find common prefixes.

  2. Comparative Analysis: The task involves comparing strings with each other to find commonalities, hence it involves comparative or relational analysis.

  3. Data Structure - Lists: The problem involves manipulating and accessing elements in a list, which is a fundamental data structure in computer science.

Language Agnostic Coding Drills

  1. Sorting: Sort a list of strings. The list is sorted lexicographically, which helps in finding the longest common prefix.

  2. String Manipulation: Analyze and manipulate strings. Here we iterate over each character of the first and last string and compare them.

  3. Iteration: Iterate through the elements of an iterable data structure like a list or string.

  4. Conditionals: Use if conditions to control the flow of the code. If a character does not match, the function returns the common prefix found so far.

  5. List Indexing: Access elements in a list using their indices.

  6. Basic Data Structures: Use of built-in data structures like lists and strings.

The difficulty of these concepts increases in the order they’re listed.

The step-by-step approach to the problem is:

  1. Sort the list of strings. The idea is that the longest common prefix of all strings will also be the longest common prefix of the first and the last string, due to the properties of lexicographical order.

  2. Initialize an empty string ans to hold the common prefix.

  3. Iterate through each character in the first and last strings (the smallest and largest string, lexicographically).

  4. Compare the characters in the same position of the first and last strings. If they match, append the character to ans.

  5. If the characters don’t match, return ans because no further common characters will be found.

  6. If all characters in the smallest string match with the corresponding characters in the largest string, return ans, which will be the longest common prefix.

  7. If no common prefix is found, ans will be an empty string and the function will return an empty string.

The concept learned in each of these steps can be practiced individually and then combined together to understand and solve the problem.

Targeted Drills in Python

Drill 1 - List Sorting:

1
2
3
4

# Given a list of strings, sort them in lexicographical order
strings = ["apple", "banana", "cherry", "applepie", "bananabread"]
strings.sort()
print(strings)

Drill 2 - String Manipulation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Given two strings, compare their characters one by one
string1 = "hello"
string2 = "help"

for s1, s2 in zip(string1, string2):
    if s1 != s2:
        print("Strings are different")
        break
else:
    print("Strings are same or one is prefix of other")

Drill 3 - List Indexing:

1
2
3
4

# Given a list, print the first and the last element
fruits = ["apple", "banana", "cherry", "dates", "elderberry"]
print("First element:", fruits[0])
print("Last element:", fruits[-1])

Drill 4 - Conditionals:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Given two numbers, print which one is bigger or if they are equal
num1 = 10
num2 = 20

if num1 > num2:
    print("num1 is bigger")
elif num1 < num2:
    print("num2 is bigger")
else:
    print("Both are equal")

Now, we integrate all these drills into one final solution for finding the longest common prefix in a list of strings:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def longestCommonPrefix(self, v: List[str]) -> str:
        ans=""
        v.sort()
        first=v[0]
        last=v[-1]
        for i in range(min(len(first),len(last))):
            if(first[i]!=last[i]):
                return ans
            ans+=first[i]
        return ans

title: Longest Common Prefix tags: linear-scan string-comparison prefix

In this article we will see how to find the longest common prefix of two strings using bruteforce approach.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def lcp(s, t)
  n = [s.size, t.size].min
  
  for i in (0..n-1)  
    if s[i] != t[i]
      return i
    end  
  end
  
  return n
end

s = 'acctgttaac'
t = 'accgttaa'

p lcp(s, t)

In this example, the longest common prefix is acc. This takes time proportional to the length of the match. Can we use this code to find the longest repeated substring in a given string? It will require two loops, with one index for the string and another index for substring. The time complexity will be quadratic.

An alternative implementation:

1
2
3
4
5
6
7
8
9

def lcp(s, t)
  i = 1
  
  while s[i] == t[i]
    i += 1
  end
  
  return i
end