[Leetcode] – Longest Common Prefix Solution

856

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”.

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.

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.

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.

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