0720. Longest Word in Dictionary ======================================================================================================================== 题目信息 -------- :题号: 0720 :难度: Medium :主题: 字符串、前缀、字典序 :原题: `LeetCode 0720 `_ :重点: 候选单词必须能从左到右逐字符扩展,且每个非空前缀都出现在输入中;长度相同时返回字典序最小者 题目重述 -------- 给定一个由小写英文字母单词组成的数组 ``words``。寻找其中最长的一个单词,使它能够从左到右一次增加一个末尾字符构造出来,并且构造过程中得到的每个非空前缀也都出现在 ``words`` 中。 若有多个符合条件的单词长度相同,返回字典序最小的那个;若没有任何单词满足条件,返回空字符串。单字符单词可以作为构造的起点。``words`` 的长度在 ``[1, 1000]`` 范围内,每个单词长度在 ``[1, 30]`` 范围内。 自建示例 -------- 逐级前缀完整: .. code-block:: text 输入:words = ["b","br","bra","bran","brand","a","at"] 输出:"brand" 解释:"brand" 的前缀 "b"、"br"、"bra" 和 "bran" 都在数组中,因此可以逐字符构造,且它比其他合法单词更长。 同长度时比较字典序: .. code-block:: text 输入:words = ["a","an","ant","ante","anti"] 输出:"ante" 解释:"ante" 和 "anti" 都能由 "a"、"an"、"ant" 逐步扩展得到,长度同为 4;"ante" 的字典序更小。 缺少单字符起点: .. code-block:: text 输入:words = ["ab","abc"] 输出:"" 解释:"ab" 缺少前缀 "a","abc" 又依赖 "a" 和 "ab"。数组中没有任何可作为起点的单字符单词,因此不存在合法候选,返回空字符串。