Home Strings [Leetcode] – Longest Common Prefix Solution

[Leetcode] – Longest Common Prefix Solution

by nikoo28
0 comment 6 mins read

In the given problem statement, we have an array of strings and we need to find the longest common prefix among them. If no common prefix exists, just return an empty string.

The starting characters of any string are called as a prefix, and the last letters are called suffix. This prefix can have any length. Among a certain set of strings, a longest common prefix will be the one that exists in every string.

Let us look at a sample test case:

Input: strs = [“club”, “clap”, “clove”]
Output: “cl”
Explanation: All the 3 strings start with the characters “cl”.

longest common prefix in a sample test case
Fig: Sample test case

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

Brute Force Solution

The most obvious way or the brute force way to solve this problem will be to start with the first letter of a string, and check if it exists in every other string.

For example, if we have an array [ "cluster", "clue", "clutch", "club", "clumsy" ], then we start with the character c and check in every other member of the array.

Fig: Brute Force approach

This is how you can start building your answer. We know that the result will contain a letter c.

Now, move on the next letter l and repeat the same process. Similarly, then move to the next character that is u.

Once you reach the next character s, we observe that it does not exist in every string. Hence, we stop right here and we have the longest common prefix with us. That is clu.

Fig: Stop as soon as you don’t find a match

Efficient Solution

The above approach is very time consuming as we have to iterate through all the strings again and again. We never take advantage of the fact that there is a “common” prefix.

This gives a clue, and we can try to sort the input array. Sorting in general will group all the similar elements together and all the elements with same prefix will be grouped together. As soon as we sort the above example we start to observe things.

Fig: Words are grouped after sorting

Now, all we need to do is match how many common characters do the first and last strings have. That is because all the strings in between will have the same common prefix.

Code

public String longestCommonPrefix(String[] strs) { StringBuilder result = new StringBuilder(); // Sort the array Arrays.sort(strs); // Get the first and last strings char[] first = strs[0].toCharArray(); char[] last = strs[strs.length - 1].toCharArray(); // Start comparing for (int i = 0; i < first.length; i++) { if (first[i] != last[i]) break; result.append(first[i]); } return result.toString(); }
Code language: Java (java)

Time Complexity: O(n \log n)
Space Complexity: O(n)

Video Explanation

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More