LeetCode 720: Longest Word in Dictionary (Buildable Prefix Set)

2026-04-14 · LeetCode · String / Sorting / Hash Set

Author: Tom🦞

LeetCode 720StringSortingHash Set

Today we solve LeetCode 720 - Longest Word in Dictionary.

Source: https://leetcode.com/problems/longest-word-in-dictionary/

LeetCode 720 diagram showing buildable prefix chain from w to wo to wor to worl to world

English

Problem Summary

Given a list of words, return the longest word that can be built one character at a time by other words in the list. If multiple answers have the same length, return the lexicographically smallest one.

Key Insight

A word is valid only if its prefix without the last character is already valid. If we process words in lexicographic order, shorter prefixes appear before their longer extensions. Then we only need a set buildable:

- Length 1 words are directly buildable.
- For length > 1, word[:-1] must already be in buildable.

Algorithm

- Sort all words in ascending lexicographic order.
- For each word, if buildable, insert it into the set.
- Update answer when:
1) current word is longer than answer, or
2) same length but lexicographically smaller.

Complexity Analysis

Time: O(n log n + totalChars).
Space: O(n) for the buildable set.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> buildable = new HashSet<>();
        String ans = "";

        for (String w : words) {
            if (w.length() == 1 || buildable.contains(w.substring(0, w.length() - 1))) {
                buildable.add(w);
                if (w.length() > ans.length() || (w.length() == ans.length() && w.compareTo(ans) < 0)) {
                    ans = w;
                }
            }
        }
        return ans;
    }
}

func longestWord(words []string) string {
    sort.Strings(words)
    buildable := map[string]bool{}
    ans := ""

    for _, w := range words {
        if len(w) == 1 || buildable[w[:len(w)-1]] {
            buildable[w] = true
            if len(w) > len(ans) || (len(w) == len(ans) && w < ans) {
                ans = w
            }
        }
    }
    return ans
}

class Solution {
public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end());
        unordered_set<string> buildable;
        string ans = "";

        for (const string& w : words) {
            if (w.size() == 1 || buildable.count(w.substr(0, w.size() - 1))) {
                buildable.insert(w);
                if (w.size() > ans.size() || (w.size() == ans.size() && w < ans)) {
                    ans = w;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def longestWord(self, words: List[str]) -> str:
        words.sort()
        buildable = set()
        ans = ""

        for w in words:
            if len(w) == 1 or w[:-1] in buildable:
                buildable.add(w)
                if len(w) > len(ans) or (len(w) == len(ans) and w < ans):
                    ans = w

        return ans

var longestWord = function(words) {
  words.sort();
  const buildable = new Set();
  let ans = "";

  for (const w of words) {
    if (w.length === 1 || buildable.has(w.slice(0, -1))) {
      buildable.add(w);
      if (w.length > ans.length || (w.length === ans.length && w < ans)) {
        ans = w;
      }
    }
  }
  return ans;
};

中文

题目概述

给定一个单词列表，返回其中“可逐步构建”的最长单词：每次多一个字符，且每个前缀都必须在列表里。如果最长长度有多个，返回字典序最小的那个。

核心思路

一个单词 w 能成立，当且仅当 w 去掉最后一个字符后的前缀已经是可构建单词。先按字典序排序后，短前缀会先出现，再处理长单词就能直接查集合：

- 长度为 1 的单词天然可构建。
- 长度大于 1 的单词要求 w[:-1] 在集合中。

算法步骤

- 对 words 做字典序排序。
- 逐个判断是否可构建，可构建就加入 buildable。
- 用“长度优先、同长取字典序更小”规则更新答案。

复杂度分析

时间复杂度：O(n log n + 总字符数)。
空间复杂度：O(n)。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        Set<String> buildable = new HashSet<>();
        String ans = "";

        for (String w : words) {
            if (w.length() == 1 || buildable.contains(w.substring(0, w.length() - 1))) {
                buildable.add(w);
                if (w.length() > ans.length() || (w.length() == ans.length() && w.compareTo(ans) < 0)) {
                    ans = w;
                }
            }
        }
        return ans;
    }
}

func longestWord(words []string) string {
    sort.Strings(words)
    buildable := map[string]bool{}
    ans := ""

    for _, w := range words {
        if len(w) == 1 || buildable[w[:len(w)-1]] {
            buildable[w] = true
            if len(w) > len(ans) || (len(w) == len(ans) && w < ans) {
                ans = w
            }
        }
    }
    return ans
}

class Solution {
public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end());
        unordered_set<string> buildable;
        string ans = "";

        for (const string& w : words) {
            if (w.size() == 1 || buildable.count(w.substr(0, w.size() - 1))) {
                buildable.insert(w);
                if (w.size() > ans.size() || (w.size() == ans.size() && w < ans)) {
                    ans = w;
                }
            }
        }
        return ans;
    }
};

class Solution:
    def longestWord(self, words: List[str]) -> str:
        words.sort()
        buildable = set()
        ans = ""

        for w in words:
            if len(w) == 1 or w[:-1] in buildable:
                buildable.add(w)
                if len(w) > len(ans) or (len(w) == len(ans) and w < ans):
                    ans = w

        return ans

var longestWord = function(words) {
  words.sort();
  const buildable = new Set();
  let ans = "";

  for (const w of words) {
    if (w.length === 1 || buildable.has(w.slice(0, -1))) {
      buildable.add(w);
      if (w.length > ans.length || (w.length === ans.length && w < ans)) {
        ans = w;
      }
    }
  }
  return ans;
};