题目链接

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

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

说明:

所有输入只包含小写字母 a-z 。

示例 1

输入: ["flower","flow","flight"]

输出: "fl"

示例 2

输入: ["dog","racecar","car"]

输出: ""

解释: 输入不存在公共前缀。

题解

public String longestCommonPrefix(String[] strs) {

    if (strs.length < 1) {

        return "";  // 数组长度小于1，直接返回默认值

    }

    StringBuilder stringBuilder = new StringBuilder();

    int minLength = Integer.MAX_VALUE;

    for (String str : strs) {

        if (str.length() == 0) {

            return "";  // 其中一个字符串长度为0，直接返回默认值

        }

        if (str.length() < minLength) {

            minLength = str.length();

        }

    }

    for (int i = 0; i < minLength; i++) {

        char prefix = strs[0].charAt(i);

        boolean flag = true;

        for (String str : strs) {

            if (str.charAt(i) != prefix) {

                flag = false;

            }

        }

        if (flag) {

            stringBuilder.append(prefix);

        } else {

            break;

        }

    }

    if (stringBuilder.toString().length() > 0) {

        return stringBuilder.toString();

    } else {

        return "";

    }

}

复杂度分析

时间复杂度：$O(n^2)$。
空间复杂度：$O(1)$。

手记

遍历即可，注意特殊值的影响，提前排除特殊情况即可。

巴特西

Java算法练习——最长公共前缀

题目链接

题目描述

示例 1

示例 2

题解

复杂度分析

手记

最新文章

热门文章