LintCode: Longest Words
Challenge
Given a dictionary, find all of the longest words in the dictionary.
Given
{
"dog",
"google",
"facebook",
"internationalization",
"blabla"
}
the longest words are(is)
["internationalization"]
.
Given
{
"like",
"love",
"hate",
"yes"
}
the longest words are
["like", "love", "hate"]
.
It's easy to solve it in two passes, can you do it in one pass?
简单题,容易想到的是首先遍历以便,找到最长的字符串,第二次遍历时取最长的放到最终结果中。但是如果只能进行一次遍历呢?一次遍历意味着需要维护当前遍历的最长字符串,这必然有比较与更新删除操作,这种情况下使用双端队列最为合适,这道题稍微特殊一点,不必从尾端插入,只需在遍历时若发现比数组中最长的元素还长时删除整个列表。
https://codesolutiony.wordpress.com/2015/06/07/lintcode-longest-words/
ArrayList<String> longestWords(String[] dictionary) {
ArrayList<String> res = new ArrayList<String>();
for (String str : dictionary) {
if (res.isEmpty() || res.get(0).length() < str.length()) {
res.clear();
res.add(str);
} else if (res.get(0).length() == str.length()) {
res.add(str);
}
}
return res;
}
ArrayList<String> longestWords(String[] dictionary) {
// write your code here
ArrayList<String> result = new ArrayList<String>();
int maxLen = 0;
for(String word : dictionary){
if(word.length() > maxLen){
result.clear();
result.add(word);
maxLen = word.length();
} else if(word.length() == maxLen){
result.add(word);
}
}
return result;
}
http://www.chenguanghe.com/lintcode-longest-words/
ArrayList<String> longestWords(String[] dictionary) {
// write your code here
ArrayList<String> res = new ArrayList<String>();
if(dictionary == null || dictionary.length == 0)
return res;
int len = dictionary[0].length();
for(int i = 0; i < dictionary.length; i++) {
if(dictionary[i].length() == len)
res.add(dictionary[i]);
else if(dictionary[i].length() > len){
len = dictionary[i].length();
res.clear();
res.add(dictionary[i]);
}
}
return res;
}
Read full article from LintCode: Longest Words