Longest Common Prefix
One of LeetCode’s easy problems is finding the longest common prefix in a array of string. The challenge description is very straightforward, given an array of string find the longest prefix that is common in all strings in the array and if none exists return an empty string. To clarify, a prefix is the first part of a word. Simply, the task is to find the longest sequence of characters that is common at the start of each string in the array.
Here is LeetCode’s given example.
Input: ["flower","flow","flight"]
Output: "fl"Input: ["dog","racecar","car"]
Output: ""
This problem, has different approaches to solving it. Right of the bat, one approach may be to build a string by looping through all the strings and characters of one string and on each iteration checking if the character exists in the other string appending the character to a prefix and iterating the next character. However, this solution is costly because we have to loop through the strings to the degree of our chosen string length.
In addition, requires handling of cases such as when the chosen string length is less than another string in the array. For example, if we loop through ‘flower’, when checking if the character ‘e’ exists in ‘flow’ the index does not exist. This approach breaks down real fast.
Let go through one approach to solving this problem. To illustrate this let’s change the input example.
Input: ["flower","flower","flower"]Given an array of three matching strings, the longest common prefix is one string in the array, in this case, ‘flower’ . Intuitively to compare matching strings, we would simply compare the individual strings, instead of comparing characters in the string. This property can be described as follows, the characters in the string ‘flower’ exists in the all the other strings.
To expand on this idea of a string containing another string, let’s look at a variation of the example.
Input: ["flow","flower"]The longest common prefix, in this example is ‘flow’ at first glance. We realize the string ‘flow’ exists in the string ‘flower’. In addition, we check if it exists at the start of the string ‘flower’. Therefore, we need to check if one string exists in the other strings.
One final variation, to illustrate one more property.
Input: ["flower","flowe","flow"]Let’s check whether the string ‘flower’ exists at the beginning of the other strings. We realize this if false. To solve this case, we can simply reduces the characters in the ‘flower’ string until we have our longest common prefix ‘flow’.
From this we can gather that any string in the array can be set as our initial prefix. Since when the string is long, we will reduce the string, the string ‘flower’ is reduced to ‘flow’.
If the string is shorter than other strings, it will exist in the other strings in our previous variation example ‘flow’ exists in ‘flower’. If only part of the shorter word is common in other strings, we will reduce it as well because it will not exactly match in all other strings.
Here is the implementation of this approach in Java.
Let’s break it down. First, we check if the array is empty and if it we return an empty string. As previously, described we can choose any string in the array as an initial prefix. This is the string that we will either check for or reduce.
Iterating over all other strings and checking if the string exists in the first position of the string using the indexOf() method. If it does not exist in the first part of the string, we reduce our prefix length by one character using the substring() method.
This approach in the worst case in this solution is O(n).
