LeetCode 最長公共前綴 [簡單]

編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 ""。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-common-prefix

示例 1:

輸入: ["flower","flow","flight"]
輸出: "fl"

示例 2:

輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共前綴。

說明

所有輸入只包含小寫字母 a-z 。

題目分析

解法1：

標(biāo)簽：鏈表
當(dāng)字符串?dāng)?shù)組長度為 0 時則公共前綴為空，直接返回
令最長公共前綴 ans 的值為第一個字符串，進(jìn)行初始化
遍歷后面的字符串，依次將其與 ans 進(jìn)行比較，兩兩找出公共前綴，最終結(jié)果即為最長公共前綴
如果查找過程中出現(xiàn)了 ans 為空的情況，則公共前綴不存在直接返回
時間復(fù)雜度：O(s)O(s)，s 為所有字符串的長度之和

作者：guanpengchn
鏈接：https://leetcode-cn.com/problems/longest-common-prefix/solution/hua-jie-suan-fa-14-zui-chang-gong-gong-qian-zhui-b/
來源：力扣（LeetCode）

解法2：

先把數(shù)組進(jìn)行排序，找到最小和最大的兩個字符串，然后從兩個字符串中找到結(jié)果返回

解法3：

選擇一個作為目標(biāo)字符串，然后逐一進(jìn)行比較切割，也就是查詢此字符串是否包含此字符串，

代碼實(shí)現(xiàn)

public class LeetCode_19_LongestCommoPrefix {

    public static void main(String[] args) {
        String[] str1 = {"flower", "flow", "flight"};
        String[] str2 = {"dog", "flow", "rececar"};
        System.out.println(longestCommonPrefix(str1));
        System.out.println(longestCommonPrefix(str2));
        System.out.println("=================");
        System.out.println(longestCommonPrefix02(str1));
        System.out.println(longestCommonPrefix02(str2));
        System.out.println("=================");
        System.out.println(longestCommonPrefix03(str1));
        System.out.println(longestCommonPrefix03(str2));
    }

    public static String longestCommonPrefix03(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String prefix = strs[0];
        for (String str : strs) {
            while (str.indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
        }
        return prefix;
    }

    public static String longestCommonPrefix02(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        Arrays.sort(strs);
        String str1 = strs[0];
        String str2 = strs[strs.length - 1];
        int i = 0;
        while (i < str1.length() && i < str2.length() && str1.charAt(i) == str2.charAt(i)) {
            i++;
        }
        if (i == 0) {
            return "";
        } else {
            return str1.substring(0, i);
        }
    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String ans = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int j = 0;
            for (; j < ans.length() && j < strs[i].length(); j++) {
                if (ans.charAt(j) != strs[i].charAt(j)) {
                    break;
                }
            }
            ans = ans.substring(0, j);
            if (ans.equals("")) {
                return "";
            }
        }
        return ans;
    }
}