The Longest Common Prefix Amongst An Array of Strings – Implementation in Javascript and PHP

Today, we’ll take a look at another easy problem on leetcode, finding the longest common prefix string amongst an array of strings.

Question

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: ["flower","flow","flight"] Output: "fl"

Example 2:

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

Note: All given inputs are in lowercase letters a-z.

Solution

My approach to the above is to keep track of a nextCharacter  variable. nextCharacter will be initiated to the first character of the first string in the array. I’ll also define an empty variable, longestPrefix to keep track of the longest prefix :).

Within a while loop, we can first check for the length of the array or the first character of the first string. If array or character is empty we return an empty string. There’s nothing much we can do here. Else, we initiate nextCharacter to the char of the first string.

We’ll use the first string in the array as our reference for checking the longest common prefix. This means, we will loop through the characters of the strings in the array, updating the nextCharacter outside of the loop, and checking if the current character of each string at the specified position is the same as the nextCharacter. If at any point, there’s a difference, regardless of which string we’re comparing, we return an empty string. Else, we keep going, appending nextCharacter to the longestPrefix variable.

Within a for loop, we begin checking each string in the array for a common prefix. We do this by checking if the character of the current string at an index is different from the nextCharacter (derived from our first string in the array), if different, we return an empty string, else, we increase a counter for moving to the next character of the first (reference) string.  We then append, nextCharacter to longestPrefix.

Implementation in Javascript

// https://leetcode.com/problems/longest-common-prefix/
/**
 * Input: ["flower","flow","flight"] Output: "fl"
 *
 * Input: ["dog","racecar","car"] Output: ""
 * Explanation: There is no common prefix among the input strings.
 */

function longestCommonPrefix(arrayOfStrings) {
    k = 0;
    firstPos = 0;
    longestPrefix = "";

    while (true) {
        if (arrayOfStrings.length === 0 || !arrayOfStrings[firstPos][k]) {
            return longestPrefix;
        }

        nextCharacter = arrayOfStrings[firstPos][k];

        for (j = 0; j < arrayOfStrings.length; j++) {
            if (arrayOfStrings[j][k] != nextCharacter) {
                return longestPrefix;
            }
        }
        k++;
        longestPrefix = `${longestPrefix}${nextCharacter}`;
    }
}

$testOne = longestCommonPrefix(["flower", "flow", "flight"]);
console.log(testOne); // "fl"

$testTwo = longestCommonPrefix(["dog", "racecar", "car"]);
console.log(testTwo); // ""

$testThree = longestCommonPrefix(["cater", "cuter", "writer"]);
console.log(testThree); // ""
// even though there is `ter` it doesn't count because we are looking longest prefix,
// so common characters should start from the beginning

Implementation in PHP

<?php

/**
 * Input: ["flower","flow","flight"] Output: "fl"
 *
 * Input: ["dog","racecar","car"] Output: ""
 * Explanation: There is no common prefix among the input strings.
 * 
 * @param $arrayOfStrings[]
 * 
 * @return string
 */
function longestCommonPrefix(array $arrayOfStrings)
{
    $k = 0;
    $firstPos = 0;
    $longestPrefix = "";

    while (true) {
        if (count($arrayOfStrings) === 0 || !$arrayOfStrings[$firstPos][$k]) {
            return $longestPrefix;
        }

        $nextCharacter = $arrayOfStrings[$firstPos][$k];

        for ($j = 0; $j < count($arrayOfStrings); $j++) {
            if ($arrayOfStrings[$j][$k] != $nextCharacter) {
                return $longestPrefix;
            }
        }

        $k++;
        $longestPrefix = $longestPrefix . $nextCharacter;
    }
}

$testOne = longestCommonPrefix(["flower", "flow", "flight"]);
echo $testOne; // "fl"

$testTwo = longestCommonPrefix(["dog", "racecar", "car"]);
echo $testTwo; // ""

$testThree = longestCommonPrefix(["cater", "cuter", "writer"]);
echo $testThree; // ""
// even though there is `ter` it doesn't count because we are looking longest prefix, 
// so common characters should start from the beginning

Do you have a different/faster approach? Please share below. Thanks for reading.

Cheers!