最長公共前綴

編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。
如果不存在公共前綴，返回空字符串 ""。

示例 1:

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

示例 2:

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

說明:

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

來源：力扣（LeetCode）

先上個人思路和代碼

public class Test14 {
    /**
     * 題目14: 最長公共前綴
     * 編寫一個函數(shù)來查找字符串?dāng)?shù)組中的最長公共前綴。如果不存在公共前綴，則返回""
     */
    public static void main(String[] args) {
        // 思路：先第一組比，得出一個正確的字符串?dāng)?shù)組
        // 后以結(jié)果數(shù)組與下一個元素比較
        // 以此往復(fù)，直到返回空字符串或遍歷完數(shù)組

        String [] data = new String[] {"abc","abcass","abcaww"};
        String result = solution(data);
        System.out.println(result);
    }

    public static String solution(String[] data) {
        if (data.length < 1) {
            return "";
        }
        if (data.length == 1) {
            return data[0];
        }
        String  temp = "";
        for (String datum : data) {
            if ("".equals(temp)) {
                temp = datum;
            } else {
                char[] chars = temp.toCharArray();
                char[] chars1 = datum.toCharArray();
                // 取兩個數(shù)組中長度最小的值，來遍歷
                int size = Math.min(chars.length, chars1.length);
                char[] result = new char[size];
                for (int i = 0; i < size; i++) {
                    if (chars[i] == chars1[i]) {
                        result[i] = chars[i];
                    } else {
                        break;
                    }
                }
                temp = String.valueOf(result);
            }
        }
        return temp;
    }
}

我的思路很簡單，比最長公共前綴，實際比較的方法就是，String.toCharArray()轉(zhuǎn)成char數(shù)組，依次比較。

其中的思路：取一個字符串做temp，每一次比較將結(jié)果記錄下來。這樣時間復(fù)雜度就是O(n)，n是字符串?dāng)?shù)組長度。同時，在遍歷的時候，如果temp結(jié)果在初始化后，又為空，那就可以認為公共前綴已經(jīng)是空字符串了。

然后，我們到Leetcode上跑下。。。。

很好，報錯了。。。

我透。。。

經(jīng)過調(diào)試修改，先看下修改后正確的代碼：

public static String solution(String[] data) {
        if (data.length < 1) {
            return "";
        }
        if (data.length == 1) {
            return data[0];
        }
        String  temp = "";
        boolean flag = false;
        for (int i = 0; i < data.length && !flag; i++) {
            String datum = data[i];
            if ("".equals(temp)  && i == 0 && !"".equals(datum)) {
                temp = datum;
            } else {
                char[] chars = temp.toCharArray();
                char[] chars1 = datum.toCharArray();
                int size = Math.min(chars.length, chars1.length);
                char[] result = new char[size];
                for (int j = 0; j < size; j++) {
                    if (chars[j] == chars1[j]) {
                        result[j] = chars[j];
                    } else {
                        if ("".equals(temp)) {
                            flag = true;
                        }
                        break;
                    }
                }
                temp = String.valueOf(result).trim();
            }
        }
        return temp;
    }

注意：剛開始的代碼，錯了大致三個地方

• break只會跳出當(dāng)前循環(huán)，我沒有考慮到當(dāng)temp已經(jīng)為""，需要跳出整個循環(huán)
• temp = datum時，需要判斷下是否是初始化狀態(tài)，字符串?dāng)?shù)組中是否含有""的情況
• 我用的是char數(shù)組作為temp，初始化時按最小的char長度初始化。這個時候，如果直接String.valueOf轉(zhuǎn)。在本地看不出來，在leetcode上會出現(xiàn)/U00000空格的情況。所以需要加trim去空格