0720. Longest Word in Dictionary

题目信息

题号:

0720

难度:

Medium

主题:

字符串、前缀、字典序

原题:

LeetCode 0720

重点:

候选单词必须能从左到右逐字符扩展,且每个非空前缀都出现在输入中;长度相同时返回字典序最小者

题目重述

给定一个由小写英文字母单词组成的数组 words。寻找其中最长的一个单词,使它能够从左到右一次增加一个末尾字符构造出来,并且构造过程中得到的每个非空前缀也都出现在 words 中。

若有多个符合条件的单词长度相同,返回字典序最小的那个;若没有任何单词满足条件,返回空字符串。单字符单词可以作为构造的起点。words 的长度在 [1, 1000] 范围内,每个单词长度在 [1, 30] 范围内。

自建示例

逐级前缀完整:

输入:words = ["b","br","bra","bran","brand","a","at"]
输出:"brand"
解释:"brand" 的前缀 "b"、"br"、"bra" 和 "bran" 都在数组中,因此可以逐字符构造,且它比其他合法单词更长。

同长度时比较字典序:

输入:words = ["a","an","ant","ante","anti"]
输出:"ante"
解释:"ante" 和 "anti" 都能由 "a"、"an"、"ant" 逐步扩展得到,长度同为 4;"ante" 的字典序更小。

缺少单字符起点:

输入:words = ["ab","abc"]
输出:""
解释:"ab" 缺少前缀 "a","abc" 又依赖 "a" 和 "ab"。数组中没有任何可作为起点的单字符单词,因此不存在合法候选,返回空字符串。