Classic 150 Interview Questions P14 Longest Common Prefix

---

Timeline

Timeline

2025-11-09

init

Trie

---

Problem:

P14 Longest Common Prefix

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

This problem can be solved by vertical scanning: look at the first letter of each string, then the second, and so on.

The following is the Trie approach:
Note: isEnd is necessary because, for example, in a Trie containing “flow” and “flower”, the size of w’s children is also 1. If we don’t mark that “flow” is an end, the traversal would continue further down.

#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();//A virtual node as the root

		// Insert all strings into the 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;
		}

		// Start from the root and follow the 'only branch' downward.
		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;
	}
};