# LWC 57：720. Longest Word in Dictionary

## LWC 57：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].

```    public String longestWord(String[] words) {
int n = words.length;
Set<String> set = new HashSet<>();
for (int i = 0; i < n; ++i){
}
String ans = "";
int maxLen = 0;
for (int i = 0; i < n; ++i){
String word = words[i];
if (valid(word, set)){
int len = word.length();
if (len >= maxLen){
if (len == maxLen){
if (ans.compareTo(word) > 0){
ans = word;
}
}
else{
ans = word;
}
maxLen = len;
}
}
}
return ans;
}

boolean valid(String word, Set<String> set){
int n = word.length();
for (int i = 0; i < n; ++i){
if (!set.contains(word.substring(0, i))) return false;
}
return true;
}```

0 条评论

## 相关文章

### Effective Testing with RSpec 3 （英文版）(序言)

Early praise for Effective Testing with RSpec 3

1844

4165

### App Guide相关

##TourGuide https://github.com/worker8/TourGuide

812

### 2018年SCI期刊最新影响因子排行，最高244，人工智能TPAMI9.455

2018年6月26日，最新的SCI影响因子正式发布，涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹，其影响因子今年再创新高，达244.585...

1462

### Knapsack problem algorithms for my real-life carry-on knapsack

I'm a nomad and live out of one carry-on bag. This means that the total weight o...

1182

2702

### java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods\$ jmod list java....

1162

### Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1866