面试经典150题 P14 最长公共前缀

---

时间轴

时间轴

2025-11-09

init

字典树

---

题目：

P14 最长公共前缀

https://leetcode.cn/problems/longest-common-prefix/description/?envType=study-plan-v2&envId=top-interview-150

这题可以直接纵向查找，看每个 string 的第一个字母，然后看第二个，以此类推。

下面写法是字典树的写法：注意：isEnd 是必需的，因为例如"flow", "flower"这个字典树，w 的 children 的 size 也为 1，如果没有表示 flow 为 end 那么会继续往下走。

#include <string>
#include <vector>
#include <unordered_map>

using std::string;
using std::vector;
using std::unordered_map;

struct Node {
	unordered_map<char, Node *> children;
	bool isEnd = false;
};

class Solution {
    public:
	string longestCommonPrefix(vector<string> &strs)
	{
		if (strs.empty())
			return "";
		Node *root = new Node();//一个虚拟节点作为根节点

		// 插入所有字符串到 Trie
		for (const string &s : strs) {
			Node *p = root;
			for (char c : s) {
				if (!p->children.count(c)) {
					p->children[c] = new Node();
				}
				p = p->children[c];
			}
			p->isEnd = true;
		}

		// 从 root 出发，沿着“唯一分支”走下去
		string prefix;
		Node *p = root;
		while (p && p->children.size() == 1 && !p->isEnd) {
			char next = p->children.begin()->first;
			prefix.push_back(next);
			p = p->children[next];
		}

		return prefix;
	}
};