c++公共前缀串字典树解法

在C++中，处理公共前缀串问题通常会使用Trie（也称为字典树或前缀树），这是一种用于高效存储和查找字符串的数据结构。当涉及到查找所有给定字符串的公共前缀时，可以按照以下步骤构建和操作Trie：

1. **构造Trie**：
- 初始化一个空节点作为根。
- 对于每个输入的字符串，从第一个字符开始遍历。
- 每次遍历到一个新的字符，就在当前节点下创建一个新的子节点，并将指针移动到新节点。
- 当遇到字符串结束时，这个路径就是该字符串的完整前缀。

2. **查找公共前缀**：
- 遍历输入的所有字符串，对每个字符串从根节点开始，如果下一个字符在当前路径上存在，则继续移动；如果不存在，则说明公共前缀已经结束。
- 当所有字符串都遍历完之后，最后一个到达的节点路径即为所有字符串的最长公共前缀。

class TrieNode {
public:
    char value;
    bool isEndOfWord;
    map<char, TrieNode*> children;

    TrieNode(char ch) : value(ch), isEndOfWord(false) {}
};

TrieNode* buildTrie(vector<string>& words) {
    TrieNode* root = new TrieNode('$');
    for (const auto& word : words) {
        TrieNode* node = root;
        for (char ch : word) {
            if (!node->children.count(ch)) {
                node->children[ch] = new TrieNode(ch);
            }
            node = node->children[ch];
        }
        node->isEndOfWord = true; // 标记单词结束节点
    }
    return root;
}

string longestCommonPrefix(vector<string>& strs) {
    TrieNode* root = buildTrie(strs);
    string prefix = "";
    TrieNode* cur = root;
    for (const string& word : strs) {
        for (char ch : word) {
            if (cur->children.find(ch) == cur->children.end()) {
                break;
            }
            cur = cur->children[ch];
        }
        if (prefix.empty()) {
            prefix = word.substr(0, cur->value != '$' ? cur->value - '$' : word.size());
        } else {
            prefix = commonPrefix(prefix, word);
        }
    }
    return prefix;
}