14. Longest Common Prefix 最长的公共字符串开头

［抄题］：

Write a function to find the longest common prefix string amongst an array of strings.

在 "ABCD" "ABEF" 和 "ACEF" 中, LCP 为 "A"

在 "ABCDEFG", "ABCEFG", "ABCEFA" 中, LCP 为 "ABC"

[暴力解法]：

时间分析：

空间分析：

［奇葩输出条件］：

［奇葩corner case］：

字符串数组为空、长度为0的情况都需要考虑

［思维问题］：

知道要从最短的前缀开始找，还以为要排序

［一句话思路］：

每个单词都用.indexof()逐个压缩前缀

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

对前缀字符串进行压缩

［复杂度］：Time complexity: O(n) Space complexity: O(1)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

int indexOf(String str): 返回指定字符串在字符串中第一次出现处的索引，如果此字符串中没有这样的字符串，则返回 -1。

若strs[i].indexOf(pre) == ，则有此前缀。这是判断前缀的新方法。

［关键模板化代码］：

每个单词都要做前缀压缩

for (int i = 1; i < n; i++) {

            while (strs[i].indexOf(pre) != 0) {

                pre = pre.substring(0, pre.length() - 1);

            }

        }

［其他解法］：

［Follow Up］：

［LC给出的题目变变变］：

[代码风格] ：

public class Solution {

    /**

     * @param strs: A list of strings

     * @return: The longest common prefix

     */

    public String longestCommonPrefix(String[] strs) {

        //corner case

        if (strs == null) {

            return "";

        }

        if (strs.length == 0) {

            return "";

        }

        //define pre

        String pre = strs[0];

        int n = strs.length;

        //shorten pre

        for (int i = 1; i < n; i++) {

            while (strs[i].indexOf(pre) != 0) {

                pre = pre.substring(0, pre.length() - 1);

            }

        }

        //return

        return pre;

    }

}

巴特西

14. Longest Common Prefix 最长的公共字符串开头

最新文章

热门文章