Longest Common Prefix

---

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.

---

Try this Problem on your own or check similar problems:

Solution:

Java

public String longestCommonPrefix(String[] strs) {
  int minLength = Integer.MAX_VALUE;
  for(String str: strs){
      if(str.length() < minLength) minLength = str.length();
  }

  int longestPrefixLength = 0;
  for(int i = 0; i < minLength; ++i){
      char c = strs[0].charAt(i);
      for(String str : strs){
          if(str.charAt(i) != c) return strs[0].substring(0, longestPrefixLength);
      }
      ++longestPrefixLength;
  }

  return strs[0].substring(0, longestPrefixLength);
}

JavaScript

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function (strs) {
  let minLength = Infinity;
  for (let str of strs) {
    if (str.length < minLength) minLength = str.length;
  }

  let longestPrefixLength = 0;
  for (let i = 0; i < minLength; ++i) {
    let c = strs[0].charAt(i);
    for (let str of strs) {
      if (str.charAt(i) !== c) return strs[0].substring(0, longestPrefixLength);
    }
    ++longestPrefixLength;
  }

  return strs[0].substring(0, longestPrefixLength);
};

Python

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        min_length = float('inf')
        for str in strs:
            if len(str) < min_length:
                min_length = len(str)

        longest_prefix_length = 0
        for i in range(min_length):
            c = strs[0][i]
            for str in strs:
                if str[i] != c:
                    return strs[0][:longest_prefix_length]
            longest_prefix_length += 1

        return strs[0][:longest_prefix_length]

C++

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int minLength = INT_MAX;
        for (const std::string& str : strs) {
            if (str.length() < minLength) minLength = str.length();
        }

        int longestPrefixLength = 0;
        for (int i = 0; i < minLength; ++i) {
            char c = strs[0][i];
            for (const std::string& str : strs) {
                if (str[i] != c) return strs[0].substr(0, longestPrefixLength);
            }
            ++longestPrefixLength;
        }

        return strs[0].substr(0, longestPrefixLength);
    }
};

---

Time/Space Complexity:

• Time Complexity: O(min(w)*n)
• Space Complexity: O(1)

---

Explanation:

Since the longest common prefix can be only smaller or equal to the length of the shortest string found in input we first determine what's the shortest string length. Then we iterate over that many characters over all strings in input until we find a mismatch (some string will have a different letter at certain index) while keeping track for the longest prefix length we found until that point. If we find a mismatch we return early from the loop otherwise the end result will be returned after the loop. By the problem statement we can be sure that input array contains at least one string but this is better to discuss with your interviewer. We have constant space complexity, while for the time complexity we have length of minimum length word in the input array O(min(w)) where for each letter we iterate over all strings in the input array of length n leading to total time complexity of O(min(w)*n).