720. Longest Word in Dictionary

Problem

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.

Example 1:

Input: 
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation: 
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

Example 2:

Input: 
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: 
Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically smaller than "apply".

Note:

• All the strings in the input will only contain lowercase letters.
• The length of words will be in the range [1, 1000].
• The length of words[i] will be in the range [1, 30].

Problem Summary

Given a string array words forming an English dictionary, find the longest word from it that can be formed by gradually adding one letter at a time using other words in the words dictionary. If there are multiple valid answers, return the word with the smallest lexicographical order among them. If there is no answer, return the empty string.

Solution Approach

• Given a string array, find the longest string that can be formed by appending one character to other strings in the string array. If there are multiple such longest strings, output the one with the smaller lexicographical order; if no such string can be found, output the empty string.
• The approach for this problem is to sort first; after sorting, the order is lexicographical from smallest to largest. Then use a map to assist with recording.

Code

package leetcode

import (
	"sort"
)

func longestWord(words []string) string {
	sort.Strings(words)
	mp := make(map[string]bool)
	var res string
	for _, word := range words {
		size := len(word)
		if size == 1 || mp[word[:size-1]] {
			if size > len(res) {
				res = word
			}
			mp[word] = true
		}
	}
	return res
}