Longest Words 133

Question

Given a dictionary, find all of the longest words in the dictionary.

Example

Given

{ "dog", "google", "facebook", "internationalization", "blabla" }

the longest words are(is) ["internationalization"].

Given

{ "like", "love", "hate", "yes" }

the longest words are ["like", "love", "hate"].

Challenge

It's easy to solve it in two passes, can you do it in one pass?

Solution

一遍法：遍历数组元素，如果当前元素长度大于之前最长元素长度，则将答案列表清空，将当前元素作为答案加入，同时更新最长元素长度；如果当前元素长度等于之前最长元素长度，则直接将当前元素作为答案加入；如果当前元素长度小于之前最长元素长度，则直接跳过。

两遍法：扫一遍求最长元素长度，再扫一遍找到所有长度为最长长度的元素。

代码如下：

class Solution {
    /**
     * @param dictionary: an array of strings
     * @return: an arraylist of strings
     */
    ArrayList<String> longestWords(String[] dictionary) {
        // write your code here
        //one pass
        ArrayList<String> res = new ArrayList<String>();
        if(dictionary == null || dictionary.length == 0){
            return res;
        }

        int max = 0;
        for(String s : dictionary){
            if(s.length() > max){
                max = s.length();
                res.clear();
                res.add(s);
            } else if(s.length() == max){
                res.add(s);
            }
        }

        return res;
    }
};