14. Longest Common Prefix

O(mn) time
vertical scan

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ''
        for x in zip(*strs):
            if len(set(x)) != 1: break
            res += x[0]
        return res

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        res = ''
        for x in zip(*strs):
            if all(c == x[0] for c in x):
                res += x[0]
            else:
                break
        return res

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        for (int i = 0; i < size(strs[0]); ++i) {
            for (int j = 1; j < size(strs); ++j) {
                if (i >= size(strs[j]) || strs[j][i] != strs[j - 1][i]) return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

horizontal scan
循环依次检查即可

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs: return ''
        res = strs[0]
        for i in range(1, len(strs)):
            res = self.resolve(res, strs[i])
            if not res:
                break
        return res

    def resolve(self, A, B):
        res = ''
        for i in range(min(len(A), len(B))):
            if A[i] != B[i]: break
            res += A[i]
        return res

trie

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Solution:

    def __init__(self):
        self.root = TrieNode()

    def add(self, s):
        p = self.root
        for c in s:
            if c not in p.children:
                p.children[c] = TrieNode()
            p = p.children[c]
        p.is_end = True

    def search(self):
        '''first approach'''
        res = ''
        p = self.root
        while len(p.children) == 1:
            k, v = list(p.children.items())[0]
            res += k
            p = v
            if p.is_end: break
        return res

    def search1(self):
        '''second approach'''
        res = ''
        p = self.root
        while len(p.children) == 1:
            res += list(p.children.keys())[0]
            p = list(p.children.values())[0]
            if p.is_end: break
        return res

    def search2(self):
        '''third approach'''
        res = ''
        p = self.root
        while len(p.children) == 1:
            res += next(iter(p.children))
            p = next(iter(p.children.values()))
            if p.is_end: break
        return res

    def longestCommonPrefix(self, strs: List[str]) -> str:
        for s in strs:
            if not s: return ''
            self.add(s)
        return self.search()

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        int n = strs.size();
        string res = strs[0];
        for (int i = 1; i < n && !res.empty(); ++i) {
            res = helper(res, strs[i]);
        }
        return res;
    }

    string helper(const string &p, const string &s) {
        int n = min(p.length(), s.length());
        string res;
        for (int i = 0; i < n && p[i] == s[i]; ++i) {
            res += p[i];
        }
        return res;
    }
};

trie

class Solution {
public:
    struct TrieNode {
        unordered_map<char, TrieNode*> children;
        bool isEnd = false;
    };
    TrieNode *root = nullptr;
    string longestCommonPrefix(vector<string>& strs) {
        root = new TrieNode;
        for (const auto &s : strs) {
            add(s);
        }
        string res;
        auto p = root;
        while (p && !p->isEnd && p->children.size() == 1) {
            auto &&[c, n] = *begin(p->children);
            res += c;
            p = n;
        }
        return res;
    }
    void add(const string &s) {
        auto p = root;
        for (char c : s) {
            if (!p->children.count(c)) {
                p->children[c] = new TrieNode;
            }
            p = p->children[c];
        }
        p->isEnd = true;
    }
};

O(mnlogn) time

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        sort(begin(strs), end(strs));
        int n = min(strs.front().length(), strs.back().length());
        string res;
        for (int i = 0; i < n && strs.front()[i] == strs.back()[i]; ++i) {
            res += strs.front()[i];
        }
        return res;
    }
};