[LeetCode] 14. Longest Common Prefix

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

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

最长公共前缀。

题意是给一组字符串，请找出这组字符串的最长公共前缀。若没有公共前缀则返回' '。这个题没有什么比较巧妙的思路，就是暴力搜索。在处理了 corner case 比如 input 为空的情况下，我们找到 input 里面的第一个单词，然后拿着这个单词的每个字母在剩下的其他单词里一个个扫，看其他单词同样位置上的字母是否一样。比如第一个例子，拿到 flower 之后，从 F 开始，看后面每个单词的第一个字母是否是 f，若是则进入下一轮，看所有单词的第二个字母是否都是 L。开始看第三个字母 O 的时候，遍历到 flight 的时候，12行的判断为 false 所以返回了str.slice(0, i)，是从第一个字母到第 i - 1 个字母组成的 substring。

时间O(n^2) - n是字母个数

空间O(1)

JavaScript实现

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function longestCommonPrefix(strs) {
    // corner case
    if (!strs.length) return '';

    // normal case
    for (let i = 0; i < strs[0].length; i++) {
        for (let str of strs) {
            if (str[i] !== strs[0][i]) {
                return str.slice(0, i);
            }
        }
    }
    return strs[0];
}

Java实现

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // corner case
        if (strs == null || strs.length == 0) {
            return "";
        }

        // normal case
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[j].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

LeetCode 题目总结