14. Longest Common PrefixLeetCode Solution

In this guide we will provide 14. Longest Common PrefixLeetCode Solution with best time and space complexity. The solution to Longest Common Prefix problem is provided in various programming languages like C++, Java and python. This will be helpful for you if you are preparing for placements, hackathon, interviews or practice purposes. The solutions provided here are very easy to follow and with detailed explanations.

Problem Statement

Complexity Analysis

Longest Common Prefix solution in C++
Longest Common Prefix soution in Java
Longest Common Prefix solution Python
Additional Resources

14. Longest Common PrefixLeetCode Solution image

Problem Statement of Longest Common Prefix

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:

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] consists of only lowercase English letters.

Complexity Analysis

Time Complexity: O(|\texttt{strs[0]}| \cdot |\texttt{strs}|)
Space Complexity: O(|\texttt{strs[0]}|)

14. Longest Common PrefixLeetCode Solution in C++

class Solution {
 public:
  string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty())
      return "";

    for (int i = 0; i < strs[0].length(); ++i)
      for (int j = 1; j < strs.size(); ++j)
        if (i == strs[j].length() || strs[j][i] != strs[0][i])
          return strs[0].substr(0, i);

    return strs[0];
  }
};
/* code provided by PROGIEZ */

14. Longest Common PrefixLeetCode Solution in Java

class Solution {
  public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0)
      return "";

    for (int i = 0; i < strs[0].length(); ++i)
      for (int j = 1; j < strs.length; ++j)
        if (i == strs[j].length() || strs[j].charAt(i) != strs[0].charAt(i))
          return strs[0].substring(0, i);

    return strs[0];
  }
}
// code provided by PROGIEZ

14. Longest Common PrefixLeetCode Solution in Python

class Solution:
  def longestCommonPrefix(self, strs: list[str]) -> str:
    if not strs:
      return ''

    for i in range(len(strs[0])):
      for j in range(1, len(strs)):
        if i == len(strs[j]) or strs[j][i] != strs[0][i]:
          return strs[0][:i]

    return strs[0]
 #code by PROGIEZ