Given a list of lowercase strings 'words', find the longest chain of words where each word in the chain (after the first) is formed by inserting exactly one character anywhere into the previous word. All words in the chain must appear in the given list. Return the chain as a list of strings in the order from shortest to longest. If there are multiple chains of the same maximum length, return the lexicographically smallest chain (compare chains lexicographically as sequences: first elements compared, if equal compare second elements, etc.). Every word may be used multiple times in forming candidate predecessors only if it appears multiple times in the input list; however, treat words with the same spelling as identical nodes for building chains (i.e., duplicates in input do not create distinct nodes). The returned chain must consist of words from the input list. Constraints: - 1 <= len(words) <= 10^4 - Each word length is between 1 and 16. - Words contain only lowercase English letters. Implement the function solve(words: list[str]) -> list[str].
['a', 'ba', 'bca', 'bda', 'bdca', 'abc', 'abcd']['a', 'ba', 'bda', 'bdca']