Interview Prep Warmup: Longest Common Prefix
“Longest Common Prefix” was originally solved on LeetCode.
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Ā
""
.
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.
Constraints
0 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] consists of only lower-case English letters.
The Problem: LeetCode’s Longest Common Prefix
Our job is to find the longest possible shared prefix among a list of strings.
Longest Common Prefix via Horizontal Scan
First: observe that the longest possible prefix cannot be longer than any one string in our list.
We’re going to assume that the first string in the list is our prefix.
Then we’ll go string by string and whittle down the prefix until it matches before moving on.
My Solution using Horizontal Scanning
This is my horizontal scan solution, it runs in O(s)
time where s
is the combined length of all strings.
/** * @param String[] $strs * @return String */ function longestCommonPrefix($strs) { if (empty($strs)) { return ""; } $nStrs = count($strs); // "Assume" the prefix is equal to the first string $prefix = $strs[0]; $pLen = strlen($prefix); for ($i = 1; $i < $nStrs; $i++) { // For the remaining strings, test against our "prefix" // If there is a common prefix, it will start at index 0 while (strpos($strs[$i], $prefix) !== 0) { // As long as the prefix doesn't match fully, remove a character and try again. $prefix = substr($prefix, 0, $pLen - 1); $pLen = strlen($prefix); // If we run out of characters, there isn't a common prefix if ($pLen == 0) { return ""; } } } return $prefix; }
Longest Common Prefix via Vertical Scan
An alternative method of solving this problem is to compare the characters column by column for each string.
We’ll still “assume” the first string is our prefix.
From there we go column by column checking that the character in that column matches. If it doesn’t, we peel it off and keep going.
In the interest of transparency: in theory this method should be at least as fast as horizontal scanning.
However: after testing them both my horizontal scan method was faster.
This is likely attributable to extra function calls I am making to get string lengths and split strings into arrays but I have not taken the time to optimize further.
My Solution using Vertical Scanning
This is my vertical scan solution, it runs in O(s)
time where s
is the combined length of all strings.
/** * @param String[] $strs * @return String */ function longestCommonPrefixVertical($strs) { if (empty($strs)) { return ""; } $nStrs = count($strs); $s0 = $strs[0]; $sA = str_split($s0); $sLen = count($sA); for ($i = 0; $i < $sLen; $i++) { $c = $sA[$i]; for ($j = 1; $j < $nStrs; $j++) { $j0 = $strs[$j]; $jA = str_split($j0); $jLen = count($jA); if ($i == $jLen || $jA[$i] != $c) { return substr($s0, 0, $i); } } } return $s0; }
Further Interview Prep
If you found this problem, or solution, helpful you should check out: Two Sum.
If you need help or found this helpful please leave a comment below!