14. Longest Common Prefix，最长相同前缀

Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"

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

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

class Trie():
    class Node():
        def __init__(self, v: str, is_word: bool) -> None:
            self.v = v
            self.is_word = is_word
            self.nexts = {}

    def __init__(self) -> None:
        self.root = Trie.Node(None,False)

    def insert(self, word: str) -> None:
        n = self.root
        for c in word:
            if c in n.nexts:
                n = n.nexts[c]
            else:
                n.nexts[c] = n = Trie.Node(c,False)
        n.is_word = True

    def lcp(self):
        """ longest common prefix """
        r = ''
        n = self.root
        while len(n.nexts)==1 and not n.is_word:
            n = tuple(n.nexts.values())[0]
            r += n.v
        return r


class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if '' in strs:
            return ''
        t = Trie()
        for s in strs:
            t.insert(s)
        return t.lcp()

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string lcp {strs[0]};
        for(auto it{strs.begin()+1}; it!=strs.end(); ++it){
            size_t j{};
            for(auto c: lcp){
                if(c != (*it)[j])
                    break;
                ++j;
            }
            lcp = lcp.substr(0,j);
        }
        return lcp;
    }
};

#define MEM_PIECE  4096

struct Trie{
private:
    struct Node{
        using ump_t = std::unordered_map<char,Node*>;
        char c;
        bool is_word { false };
        bool is_avail { false };
        uint32_t sidx {};
        ump_t *nexts;

        Node(char c);
        ~Node();
    };
    static_assert(sizeof(Node) == 16);
    static_assert(MEM_PIECE%sizeof(Node) == 0);

public:
    Node root {0};
    Trie();
    ~Trie();
    void insert(std::string s);
    bool query(std::string s) noexcept;
    std::string lcp() noexcept;

private:
    const static uint32_t nslot { MEM_PIECE/sizeof(Node) };
    std::vector<Node*> mem;
    std::deque<uint32_t> avail_slot;
    std::pair<Node*,uint32_t> get_mem();
    void del_mem(Node *n) noexcept;
};


Trie::Trie(){
    root.nexts->reserve(256);
}


Trie::Node::Node(char c): c{c}{
    nexts = new ump_t;
    nexts->reserve(4);
}


Trie::Node::~Node(){
    delete nexts;
}


pair<Trie::Node*,uint32_t> Trie::get_mem(){
    if(avail_slot.empty()){
        Node *pm { (Node*)(new char[nslot*sizeof(Node)]) };
        mem.push_back(pm);
        uint32_t msize { (uint32_t)mem.size() };
        for(uint32_t i{(msize-1)*nslot+1}; i<msize*nslot; ++i)
            avail_slot.push_back(i);
        for(uint32_t i{1}; i<nslot; ++i)
            (pm+i)->is_avail = true;
        return {pm, (msize-1)*nslot};
    }

    uint32_t sidx { avail_slot[0] };
    uint32_t a { sidx / nslot };
    uint32_t b { sidx % nslot };
    avail_slot.pop_front();
    return {mem[a]+b, sidx};
}


void Trie::del_mem(Trie::Node *n) noexcept{
    n->~Node();
    n->is_avail = true;
    avail_slot.push_back(n->sidx);
}


void Trie::insert(string s){
    if((s=="") || query(s))
        return;
    Node *n {&root};
    for(auto c: s){
        if(n->nexts->find(c) == n->nexts->end()){
            auto [p,sidx] { get_mem() };
            (*n->nexts)[c] = new(p) Node{c};
            assert((*n->nexts)[c]->is_avail == false);
            (*n->nexts)[c]->sidx = sidx;
        }
        n = (*n->nexts)[c];
    }
    n->is_word = true;
}


bool Trie::query(string s) noexcept{
    Node *n {&root};
    auto not_found {n->nexts->end()};
    for(auto c: s){
        if(n->nexts->find(c) == not_found){
            return false;
        }
        n = (*n->nexts)[c];
    }
    bool r = n->is_word;
    return r;
}


string Trie::lcp() noexcept{  // longest common prefix
    string r;
    Node *n {&root};
    while((n->nexts->size()==1) && (!n->is_word)){
        char c { n->nexts->begin()->second->c };
        r += c;
        n = (*n->nexts)[c];
    }
    return r;
}


Trie::~Trie(){
    for(auto it{mem.begin()}; it!=mem.end(); ++it){
        for(uint32_t j{}; j<nslot; ++j)
            if((*it+j)->is_avail == false)
                (*it+j)->~Node();
        delete[] (char*)*it;
    }
}


class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        Trie t;
        for(auto &s: strs){
            if(s == "")
                return "";
            t.insert(s);
        }
        return t.lcp();
    }
};

char* longestCommonPrefix(char **strs, int strsSize){
    static char lcp[201] = {};
    strcpy(lcp, strs[0]);
    for(int i=1; i<strsSize; ++i){
        int j = 0;
        for(; j<strlen(lcp); ++j){
            if(lcp[j] != strs[i][j])
                break;
        }
        lcp[j] = 0;
    }
    return lcp;
}