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 instrs[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