# Longest Common Prefix | Leetcode #14 | Easy

--

In this post I will discuss the solution to the leetcode problem — Longest Common Prefix.

## Problem:

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.

## Solution:

The algorithm is as follows —

1. If the input array of strings is empty, return `""` as there is no solution.
2. Let’s assume the first string in input is the longest common prefix and hence set `output = strs[0]`
3. Iterate over rest of the strings in the input array and for each of the strings follow steps from #4 to #5
4. What we can do now is to check if the output string is found in`strs[i]` . We can do that by using `indexOf()` function. If we are able to find the output string in the `strs[i]` , then we are good and move on to the next string in the input array.
5. Otherwise, we would need to reduce the output string from the end by 1 character. We can do that by using `substring()` function. Now that the `output` string’s length is reduced, we continue matching it within `strs[i]`
6. In worst case, we either reduce the output string from `strs[0]` to an empty string or we have a substring of `strs[0]` that matches in all the strings in the input array. We return the output.

This is how the solution looks like —

`public String longestCommonPrefix(String[] strs) {    if (strs.length == 0) {        return "";    }    String output = strs[0];    for (int i = 1; i < strs.length; i++) {        while(strs[i].indexOf(output) != 0) {            output = output.substring(0, output.length() - 1);        }    }    return output;}`

Hope this helps! Happy coding! 🙂

If you think the solution can be improved or misses something, feel free to comment. There is always some room for improvement.

Find the solutions to the leetcode problems here — https://github.com/rishikeshdhokare/leetcode-problems

--

--

I am a Software Engineer from India and working in Berlin, Germany. I write about technology, my experiences in Germany, travel in Europe.