最长公共前缀

查找字符串数组中的最长公共前缀

class Solution {
    /**
     * 查找字符串数组中的最长公共前缀。
     *
     * 该方法使用二分查找来优化寻找最长公共前缀的过程。
     * 它通过二分查找确定最长公共前缀的长度，然后通过逐字符比较来验证该长度是否是所有字符串的公共前缀。
     *
     * @param strs 字符串数组
     * @return 最长公共前缀，如果数组为空或没有公共前缀，则返回空字符串 ""
     */
    public String longestCommonPrefix(String[] strs) {
        // 1. 边界情况处理：如果数组为空或为 null，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 2. 找到最短字符串的长度：最长公共前缀的长度不可能超过最短字符串的长度
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }

        // 3. 初始化二分查找的左右边界
        int low = 0, high = minLength;

        // 4. 二分查找：在 [0, minLength] 的范围内进行二分查找，寻找最长公共前缀的长度
        while (low < high) {
            // 5. 计算中间值：注意 + 1，防止 low 和 high 相邻时，mid 始终等于 low，导致死循环
            int mid = (high - low + 1) / 2 + low;

            // 6. 判断长度为 mid 的前缀是否是所有字符串的公共前缀
            if (isCommonPrefix(strs, mid)) {
                // 7. 如果是公共前缀，那么最长公共前缀的长度至少为 mid，更新 low = mid
                low = mid;
            } else {
                // 8. 如果不是公共前缀，那么最长公共前缀的长度小于 mid，更新 high = mid - 1
                high = mid - 1;
            }
        }

        // 9. 循环结束后，low 的值就是最长公共前缀的长度，返回 strs[0].substring(0, low)
        return strs[0].substring(0, low);
    }

    /**
     * 判断长度为 length 的前缀是否是所有字符串的公共前缀。
     *
     * @param strs   字符串数组
     * @param length 前缀的长度
     * @return 如果长度为 length 的前缀是所有字符串的公共前缀，则返回 true；否则返回 false
     */
    public boolean isCommonPrefix(String[] strs, int length) {
        // 1. 从第一个字符串中提取长度为 length 的前缀
        String str0 = strs[0].substring(0, length);

        // 2. 获取字符串数组的长度
        int count = strs.length;

        // 3. 遍历剩余的字符串，将每个字符串的前 length 个字符与 str0 进行比较
        for (int i = 1; i < count; i++) {
            String str = strs[i];

            // 4. 逐字符比较
            for (int j = 0; j < length; j++) {
                // 5. 如果发现任何一个字符串的前 length 个字符与 str0 不相同，则返回 false
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }

        // 6. 如果所有字符串的前 length 个字符都与 str0 相同，则返回 true
        return true;
    }
}