Longest Words

Question

  1. Given a dictionary, find all of the longest words in the dictionary.
  3. Example
  4. Given
  6. {
  7.   "dog",
  8.   "google",
  9.   "facebook",
  10.   "internationalization",
  11.   "blabla"
  12. }
  13. the longest words are(is) ["internationalization"].
  15. Given
  17. {
  18.   "like",
  19.   "love",
  20.   "hate",
  21.   "yes"
  22. }
  23. the longest words are ["like", "love", "hate"].
  25. Challenge
  26. It's easy to solve it in two passes, can you do it in one pass?

题解

简单题，容易想到的是首先遍历以便，找到最长的字符串，第二次遍历时取最长的放到最终结果中。但是如果只能进行一次遍历呢？一次遍历意味着需要维护当前遍历的最长字符串，这必然有比较与更新删除操作，这种情况下使用双端队列最为合适，这道题稍微特殊一点，不必从尾端插入，只需在遍历时若发现比数组中最长的元素还长时删除整个列表。

Java

  1. class Solution {
  2.     /**
  3.      * @param dictionary: an array of strings
  4.      * @return: an arraylist of strings
  5.      */
  6.     ArrayList<String> longestWords(String[] dictionary) {
  7.         ArrayList<String> result = new ArrayList<String>();
  8.         if (dictionary == null || dictionary.length == 0) return result;
  10.         for (String str : dictionary) {
  11.             // combine empty and shorter length
  12.             if (result.isEmpty() || str.length() > result.get(0).length()) {
  13.                 result.clear();
  14.                 result.add(str);
  15.             } else if (str.length() == result.get(0).length()) {
  16.                 result.add(str);
  17.             }
  18.         }
  20.         return result;
  21.     }
  22. }

源码分析

熟悉变长数组的常用操作。

复杂度分析

时间复杂度 O(n), 最坏情况下需要保存 n - 1个字符串，空间复杂度 O(n).

Reference