力扣十四题. 最长公共前缀

* 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"
1
2

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。
1
2
3

提示：

1 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] 仅由小写英文字母组成

Java题解

思路

首先我们可以根据题意可以知道数组字符串可能存在为空的情况，就需要分两种情况进行代码书写

解题方法

如果数组字符串为空 就直接输出空字符 如果不为空 就先将数组第一个字符串定位相同前缀 再依次进行遍历 根据下标找 出最长公共前缀

复杂度

时间复杂度:

O(mn)，其中 m 是字符串数组中的字符串的平均长度，n 是字符串的数量。最坏情况下，字符串数组中的每个字符串的每个字符都会被比较一次。

空间复杂度:

O(1)。使用的额外空间复杂度为常数。

code

```java
public class LongestPrefix {
    public static String longestCommonPrefix(String[] strs) {
        // 首先判断数组字符串是否为空
        if (strs == null || strs.length == 0){
            return "";
        }
        // 如果不为空，将第一个数组字符串赋值给prefix
        String prefix = strs[0];
        // 遍历数组字符串，得出最长公共前缀
        for (int i = 1; i < strs.length; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
        }
        return prefix;
    }

    public static String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int commonPrefixLength = length;
        for (int i = 0; i < length && commonPrefixLength == length; i++) {
            if (str1.charAt(i) != str2.charAt(i)) {
                commonPrefixLength = i;
            }
        }
        return str1.substring(0, commonPrefixLength);
    }

    public static void main(String[] args) {
        String[] arr = {"flower","flow","flight"};
        String s = LongestPrefix.longestCommonPrefix(arr);
        System.out.println(s);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

1