Interview Classic 150 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 character of each string, then the second, and so on.

The following is the Trie approach:
Note: isEnd is necessary because, for example, in the Trie for “flow” and “flower”, the children size of ‘w’ is also 1. If we don’t mark ‘flow’ as end, it will continue further.

#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 dummy node as 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 root and go down along the 'only branch'
		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;
	}
};