力扣14 尋找字元串數組中最長公共首碼

力扣14 尋找字元串數組中最長公共首碼

題目：

編寫一個函數來查找字元串數組中的最長公共首碼。

如果不存在公共首碼，返回空字元串 ""。

示例 1：

輸入：strs = ["flower","flow","flight"]
輸出："fl"

示例 2：

輸入：strs = ["dog","racecar","car"]
輸出：""
解釋：輸入不存在公共首碼。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 僅由小寫英文字母組成

解題思路：

首先我們需要將這個字元串數組進行排序，然後找到這個字元串數組中最短的字元串，因為進行迴圈比較的時候比較的次數不會超過最短的字元串的長度。進行排序後之後的數組我們僅僅比較第一個字元串與最後一個字元串即可。

代碼：

import java.util.Arrays;

/**
 * 返回一個字元串數組中的最長的公共首碼。
 * 首先我們可以對這個數組進行排序,然後比較排序之後的第一個字元串與最後一個字元串
 * 的元素是否相同,可以明確的是最多比較的次數是最短字元串的長度
 */
public class MaxLengthSubStrings {
    public static void main(String[] args) {
        String[] strings = {"abc","abcd","abdsc","abcwsed"};
        String s = maxLengthSubString(strings);
        System.out.println("s = " + s);
    }
    //定義一個方法獲得最長的公共首碼,返回值類型為String參數為String[] str
    public static String maxLengthSubString(String[] str){
        if (str == null || str.length == 0) {
            return null;
        }
        if (str.length == 1) {
            return str[0];
        }
        int len = str.length;
        //對數組進行排序
        Arrays.sort(str);
        String firstStr = str[0];
        String lastStr = str[len - 1];
        //定義一個StringBuilder用來接收最長的公共首碼
        StringBuilder stringBuilder = new StringBuilder();
        //取得字元串數組中的最短字元串的長度
        int minLength = Math.min(firstStr.length(),lastStr.length());
        //判斷第一個字元串與最後一個字元串相同的字元
        for (int i = 0; i < minLength; i++) {
            if(firstStr.charAt(i) == lastStr.charAt(i)){
                //如果字元相等就添加進stringBuilder
                stringBuilder.append(firstStr.charAt(i));
            }else {
                //否則就退出比較
                break;
            }
        }
        return stringBuilder.toString();
    }
}