# Longest Words ### Source - lintcode: [(133) Longest Words](http://www.lintcode.com/en/problem/longest-words/) ~~~ 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? ~~~ ### 題解 簡單題，容易想到的是首先遍歷以便，找到最長的字符串，第二次遍歷時取最長的放到最終結果中。但是如果只能進行一次遍歷呢？一次遍歷意味著需要維護當前遍歷的最長字符串，這必然有比較與更新刪除操作，這種情況下使用雙端隊列最為合適，這道題稍微特殊一點，不必從尾端插入，只需在遍歷時若發現比數組中最長的元素還長時刪除整個列表。 ### Java ~~~ class Solution { /** * @param dictionary: an array of strings * @return: an arraylist of strings */ ArrayList<String> longestWords(String[] dictionary) { ArrayList<String> result = new ArrayList<String>(); if (dictionary == null || dictionary.length == 0) return result; for (String str : dictionary) { // combine empty and shorter length if (result.isEmpty() || str.length() > result.get(0).length()) { result.clear(); result.add(str); } else if (str.length() == result.get(0).length()) { result.add(str); } } return result; } } ~~~ ### 源碼分析 熟悉變長數組的常用操作。 ### 復雜度分析 時間復雜度 O(n)O(n)O(n), 最壞情況下需要保存 n - 1個字符串，空間復雜度 O(n)O(n)O(n). ### Reference - [Lintcode: Longest Words | codesolutiony](https://codesolutiony.wordpress.com/2015/06/07/lintcode-longest-words/)