Leetcode #14 — Longest Common Prefix

Hello everyone, today we’ll be looking at the Longest Common Prefix problem. This question is marked as “Easy” on Leetcode.

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 "".

Examples from Leetcode

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Solution

Submission on Leetcode

Explanation (with two examples)

1. Let's call: longestCommonPrefix(["flower","flow","flight"])
- Length of the input list is not 0, so the if condition fails.
- min_string = min(strs) = flight
- max_string = max(strs) = flower
- enumerate(min_string) would result:
idx ... letter
 0  ...  f
 1  ...  l
 2  ...  i
 3  ...  g
 4  ...  h
 5  ...  t
- With that in mind, check if letter != max_string. This is true when letter is 'i' from min_string, which is 'flight' and max_string[idx] where idx = 2, then max_string[2] = o. 
- Return min_string[:idx] = 'flight'[:idx] = 'fl'.
2. Let's call: longestCommonPrefix(["drake", "drone", "drastic"])
- Length of the input list is not 0, so the if condition fails.
- min_string = min(strs) = drake
- max_string = max(strs) = drone
- enumerate(min_string) would result: 
idx ... letter
 0  ...  d
 1  ...  r
 2  ...  a
 3  ...  k
 4  ...  e
- With that in mind, check if letter != max_string. This is true when letter is 'a' from min_string, which is 'drake' and max_string[idx] where idx = 2, then max_string[2] = o.
- Return min_string[:idx] = 'drake'[:idx] = 'dr'.

That’s all, folks! Happy learning!

Dhairya Dave