题目描述

给你一个大小为n的字符串数组strs，其中包含n个字符串，编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围：0<=n<=5000, 0<=len(strs[i])<=5000

例1
输入：["abca","abc","abca","abc","abcc"]
返回值："abc"

题目分析

想要获取数组中所有字符串的最长公共前缀，需要遍历每个字符串的字符，进行比较，比较的方法主要有两种：
①横向比较：先比较两个字符串的最长前缀，后面用前面得到的前缀不断与后面进行比较，得到最终的结果。
②纵向比较：可以对每个字符串的第一个、第二个...字符依次比较，直到有一个字符串不满足与其他字符串相同的条件就可以将前面累计的字符结果返回。

解题思路

方法1：横向比较

横向比较的过程比较简单，主要是对两个字符串的最长前缀进行比较，从第一个和第二个的比较结果，一直到最后一个字符串，比较过程如下：

因为横向比较会重复比较前面比较过了的前缀部分，所以时间花费上相比纵向比较会更多。

方法2：纵向比较

纵向比较，需要一个记录结果的字符对象，对所有的字符串前缀依次进行比较，所有字符串都满足的字符记录到字符对象中，只要有一个不符合就可以直接返回对象结果，这里面主要是处理对何时返回对象结果的判断：
①当判断的字符到达某个字符串的尾部时，返回；
②当判断的字符不符合某个字符串的前缀时，返回；
③只有所有的字符串的前缀比较都通过后，才会将结果记录下来。

代码实现

方法1：横向比较

import java.util.*;

public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        if(strs == null || strs.length == 0) return "";
        if(strs.length == 1) return strs[0];
        // 横向比较字符串的最长前缀
        // 先获取第一个和第二个字符创最长公共前缀
        String same = getSimilar(strs[0], strs[1]);
        for(int i=2;i<strs.length;i++){
            // 将前面的最长公共前缀和后面的字符串进行求前缀
            same = getSimilar(same, strs[i]);
        }
        return same.toString();
    }
    
    public String getSimilar(String s1, String s2){
        String res = "";
        // 两个字符串求最长前缀的过程，从头开始比较判断
        for(int i=0; i<s1.length() && i<s2.length(); i++){
            if(s1.charAt(i) == s2.charAt(i)){
                res += s1.charAt(i);
            }else{
                break;
            }
        }
        return res;
    }
}

时间复杂度：$O\left(nm\right)O(nm)$O(nm)，n是字符串数组长度，nm是字符串数组中所有的字符的数量，横向比较的过程最差需要遍历所有的字符，所以时间复杂度为$O\left(nm\right)O(nm)$O(nm)；

空间复杂度：$O\left(1\right)O(1)$O(1)，只需要常数级别变量。

方法2：纵向比较

import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        // write code here
        if(strs == null || strs.length == 0) return "";
        if(strs.length == 1) return strs[0];
        // 存储最长前缀
        StringBuilder res = new StringBuilder("");
        boolean flag = true;
        int index = 0;
        char test = ' ';
        while(flag){
            // 对数组中的字符串进行纵向判断
            for(int i=0;i<strs.length;i++){
                String str = strs[i];
                // 对第index个字符进行判断
                // 对于第一个字符串，未到字符串尾部，设置判断字符为index位上的
                if(i == 0 && index < str.length()){
                    test = str.charAt(index);
                }
                // 对于后面的字符串，需要判断是否与判断字符相同
                if(i > 0 && index <str.length() && str.charAt(index) != test){
                    flag = false;
                    break;
                }
                // 中间长度不够的直接返回
                if(test != ' ' && index >= str.length()){
                    flag = false;
                    break;
                }
                // 当前面的字符串都判断完了，就可以加入结果中
                if(i == strs.length-1){
                    if(test != ' ' && index < str.length()){
                        res.append(test);
                    }else{
                        flag = false;
                        break;
                    }
                }
            }
            index++;
        }
        return res.toString();
    }
}

时间复杂度：$O\left(nm\right)O(nm)$O(nm)，n是字符串数组长度，nm是字符串数组中所有的字符的数量，纵向比较的过程最差需要遍历所有的字符，所以时间复杂度为$O\left(nm\right)O(nm)$O(nm)；

空间复杂度：$O\left(1\right)O(1)$O(1)，只需要常数级别变量。