Understanding the Problem
We are given an array of strings and our task is to find the longest common prefix — that is, the longest sequence of characters starting from the beginning that is shared by all strings in the array.
To understand this, imagine writing all the strings in a vertical column and comparing characters column by column (from top to bottom, left to right). As soon as one character doesn’t match across any string, we stop. Everything before that point is our answer.
Step-by-Step Solution with Example
Step 1: Choose a Reference
We begin by using the first string as a reference. This gives us a starting point to compare with the rest of the strings.
Step 2: Vertical Scanning
We scan each character of the first string one by one. For each character, we check whether all other strings have the same character at the same position.
Step 3: Stop at the First Mismatch
If we find a character that does not match in any of the strings, we stop and return the part of the string matched so far — that is our longest common prefix.
Step 4: Example with [ "flower", "flow", "flight" ]
- Start with "flower" as the reference.
- Compare character at position 0: all strings have 'f' ✅
- Compare character at position 1: all strings have 'l' ✅
- Compare character at position 2: "flower" and "flow" have 'o', but "flight" has 'i' ❌
- We stop at position 2 — the common prefix is
"fl"
.
Step 5: Return Result
Return the substring of the first string from index 0 up to the position where the mismatch occurred. This is our final answer.
Edge Cases
- No match at all: [ "dog", "racecar", "car" ] → No characters match at index 0, so return
""
.
- Single string: [ "a" ] → Only one string, so return that string itself.
- Some string is empty: [ "abc", "" ] → One string is empty, so return
""
.
- Empty array: [ ] → No strings to compare, return
""
.
- All strings are identical: [ "apple", "apple", "apple" ] → All characters match, return
"apple"
.
Finally
This approach is known as vertical scanning. It’s simple and efficient — as soon as one character differs, we stop and return the prefix matched so far.
Handling edge cases early helps us avoid unnecessary work and keeps the solution clean. This method is ideal for beginners as it closely follows the intuition of comparing letters line by line.
Comments
Loading comments...