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!