LeetCode 14. 最长公共前缀

摘要：
很简单的模拟题，如果换成公共子序列那就复杂了。

题目

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

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

示例 1：

输入：strs = [“flower”,”flow”,”flight”]
输出：”fl”

示例 2：

输入：strs = [“dog”,”racecar”,”car”]
输出：””
解释：输入不存在公共前缀。

提示：

• $0 <= strs.length <= 200$
• $0 <= strs[i].length <= 200$
• $strs[i]$ 仅由小写英文字母组成

按列比较

可以拿第一个字符串作为比较对象，维护一个单指针，当单指针超出第一个字符串的下标范围则可以认为第一个字符串就是所有字符串中最短的，且是公共前缀；
否则拿当前指针指向的第一个字符串的字符和所有字符串该位置的字符比较，一旦出现不匹配的情况那到此为指针前面的所有前缀串就是最长公共子串。

• C++
• Java

class Solution {
public:
    string longestCommonPrefix(vector<string>& ss) {
        int n = ss.size();
        if (!n) return "";
        string res;
        for (int i = 0;; ++i) {
            if (i >= ss[0].size()) {
                return ss[0];
            }
            char c = ss[0][i];
            for (int j = 0; j < n; ++j) {
                if (ss[j][i] != c) {
                    return res;
                }
            }
            res += c;
        }
        return res;
    }
};

class Solution {
    public String longestCommonPrefix(String[] ss) {
        int n = ss.length;
        if (n == 0) return "";
        StringBuilder res = new StringBuilder();
        for (int i = 0;; ++i) {
            if (i >= ss[0].length()) return ss[0];    // 第一个字符串在所有串中最短
            char c = ss[0].charAt(i);
            for (String s : ss) {
                if (i >= s.length() || s.charAt(i) != c) return res.toString();
            }
            res.append(c);
        }
    }
}

复杂度：最坏的情况下，需要将每一个字符枚举到，所以复杂度为所有字符的数量之和。

原题链接： LeetCode 14. 最长公共前缀