Description

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:

1Input: strs = ["flower","flow","flight"]
2Output: "fl"

Example 2:

1Input: strs = ["dog","racecar","car"]
2Output: ""
3Explanation: 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.

Solution

It looks like this requires traversal over all elements of strs array and for each string of this array, we need to check each character at a time. If we start traversal from top to bottom, we can check at which stage the character is not present in one of the strings and we can exit at that point. We start by iterating through all characters of first string. Inside, this iteration, we check each of the strings other than first string. If at any point, we have reached end of string or characters for first does not match any of the string’s corresponding character, that means we have found the maximum substring and we return that initial matching substring section. If we finish the iteration and this condition didn’t succeed, that means first string itself is the longest common prefix.

1if strs is null OR strs.length == 0
2    return ""
3first = strs[0]
4for (int i = 0; i < first.length(); i++)
5    for (int j = 1; j < strs.length; j++)
6        if (i == strs[j].length || strs[j].charAt(i) != first.charAt(i))
7            return first.substring(0, i)
8    return first

 1class Solution {
 2    public String longestCommonPrefix(String[] strs) {
 3        if (strs == null || strs.length == 0)
 4            return "";
 5        String first = strs[0];
 6        for (int i = 0; i < first.length(); i++) {
 7            char c = first.charAt(i);
 8            for (int j = 1; j < strs.length; j++) {
 9                if (i == strs[j].length() || strs[j].charAt(i) != c) {
10                    return first.substring(0, i);
11                }
12            }
13        }
14        return first;
15    }
16}