720. 词典中最长的单词

蔚落 2023-10-05 20:38 64阅读 0赞

给出一个字符串数组`words`组成的一本英语词典。从中找出最长的一个单词，该单词是由`words`词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。

若无答案，则返回空字符串。

**示例 1：**

输入：
    words = ["w","wo","wor","worl", "world"]
    输出："world"
    解释： 
    单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

**示例 2：**

输入：
    words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
    输出："apple"
    解释：
    "apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply"。

**提示：**

*  所有输入的字符串都只包含小写字母。
 *  `words`数组长度范围为`[1,1000]`。
 *  `words[i]`的长度范围为`[1,30]`。

import java.util.Arrays;
    
    public class Solution720 {
    	public String longestWord(String[] words) {
    		Arrays.sort(words);
    		System.out.println(Arrays.toString(words));
    		int maxlen = 0;
    
    		for (int i = 0; i < words.length; i++) {
    			if (words[i].length() > maxlen) {
    				maxlen = words[i].length();
    			}
    		}
    		int count = 0;
    		// System.out.println(maxlen);
    		// System.out.println(maxword);
    
    		for (int j = maxlen; j > -1; j--) {
    
    			for (int i = 0; i < words.length; i++) {
    				// System.out.println(words[i]);
    				if (words[i].length() == j) {
    					count = 0;
    
    					for (int k = 0; k <= words[i].length(); k++) {
    
    						for (int l = 0; l < words.length; l++) {
    
    							// System.out.println(words[i].substring(0, k));
    							if (words[i].substring(0, k).equals(words[l])) {
    								count++;
    								break;
    							}
    
    						}
    
    						// System.out.println(count);
    					}
    					if (count == words[i].length()) {
    						return words[i];
    					}
    				}
    			}
    		}
    
    		return "";
    	}
    
    	public static void main(String[] args) {
    
    		Solution720 s = new Solution720();
    		String[] words = { "w", "wo", "wor", "worl", "world" };
    
    		System.out.println(s.longestWord(words));
    	}
    }