The LeetCode problem “Longest Common Prefix” requires finding the longest common starting sequence (prefix) among an array of strings. For example, given [“flower”, “flow” “flight”], the longest common prefix is “fl”.
Algorithm and Data Structure Choice
Chosen Algorithm: Vertical Scanning
The vertical scanning technique checks each character position across all strings simultaneously, moving vertically down each column of characters from the beginning. This approach continues until a mismatch is found or the end of the shortest string is reached.
1. Array of Strings with Shared Characteristics: If the problem involves finding a common pattern or characteristic across multiple strings, vertical scanning is an efficient option for checking alignment.
2. Prefix-Specific Requirement: The problem specifically asks for the longest common prefix, not the longest common substring or suffix, making it ideal for a character-by-character scan starting from the beginning.
3. Early Termination on Mismatch: Vertical scanning works well when a mismatch in one position means we can immediately stop checking further, thus making the algorithm efficient.
Vertical scanning is similar to algorithms that perform line-by-line or column-by-column checks across rows of data, making it well-suited for problems involving alignment or character matching. It’s often used in string comparison problems where alignment or consistency across all elements is needed.
High-Level Algorithm Steps
1. Edge Case Check: If the array is empty, return an empty string.
2. Loop Through Characters by Position:
• For each character position (starting from the first position), compare the character across all strings.
3. Check for Mismatch:
• If a mismatch is found, stop and return the prefix up to the previous position.
• If no mismatch is found for the position, continue to the next position.
4. Return Full Prefix if No Mismatch:
• If all characters match up to the end of the shortest string, return the accumulated prefix.
public class Solution {
public String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return ""; // Edge case for empty array
// Loop through each character position of the first string
for (int i = 0; i < strs[0].length(); i++) {
char c = strs[0].charAt(i); // Current character from the first string
// Compare this character with the same position in all other strings
for (int j = 1; j < strs.length; j++) {
// If mismatch or end of string is reached, return the current prefix
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}
}
}
// All characters matched for the full length of the first string
return strs[0];
}
}
Line-by-Line Explanation
- Check for Empty Input
if (strs == null || strs.length == 0) return "";- If the aarray is empty or null, there’s no common prefix to find, so we return an empty string as specified by the problem
2. Loop Through Character Positions of the First String
for (int i = 0; i < strs[0].length(); i++) {- We use the first string in the array as a reference. This loop iterates over each character position in the first string.
3. Retrieve Character from First String:
char c = strs[0].charAt(i);- We get the character at the current position i from the first string. This character will be compared against the characters in the same position in all other string.
4. Loop Through Remaining Strings
for (int j = 1; j < strs.length; j++) {- This inner loop iterates through each of the remaining strings to check if they have the same character at position i.
5. Check for Mismatch or End of String
if (i >= strs[j].length() || strs[j].charAt(i) != c) {
return strs[0].substring(0, i);
}- If any string is shorter than i (i.e., we reach the end of that string), or if the character at position i does not match c, we immediately return the common prefix up to this point. The prefix is extracted as strs[0].substring(0, i).
6. Return Full Prefix if No Mismatch
return strs[0];
• If the loop completes without finding a mismatch, it means the entire first string is a common prefix among all strings, so we return it.
Why This Code Was Coded This Way
• Efficiency: By choosing the first string as the reference and comparing characters vertically across all strings, the algorithm minimizes redundant comparisons and can stop early when a mismatch is found.
• Simplicity: Using substring(0, i) to return the prefix up to the mismatch point keeps the code clean and avoids complex handling of indexes.
• Direct Approach: The algorithm addresses the problem directly by working through each character position rather than generating and checking possible prefixes, making it both time-efficient and straightforward.
This solution uses vertical scanning to efficiently determine the longest common prefix, making it well-suited for cases where early mismatches can reduce unnecessary work.
