Longest Words
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?
////First，tracking the array to record every word‘s length, and find out the max length
////the second loop is to find out specific words.
/// keep in mind how to initiate the int array.
class Solution { /** * @param dictionary: an array of strings * @return: an arraylist of strings */ ArrayList<String> longestWords(String[] dictionary) { // write your code here ArrayList<String> newString=new ArrayList<String>(); int count[]=null; int m=dictionary.length; count=new int[m]; int max=0; for(int i=0;i<dictionary.length;i++) { int n=dictionary[i].length(); count[i]=n; max=Math.max(n,max); } for(int i=0;i<dictionary.length;i++) { if(count[i]==max) { newString.add(dictionary[i]); } } return newString; }
if we use hashtable, we can do it in one pass
following is the code,
class Solution { /** * @param dictionary: an array of strings * @return: an arraylist of strings */ ArrayList<String> longestWords(String[] dictionary) { // write your code here HashMap<Integer,ArrayList<String>> map=new HashMap<Integer,ArrayList<String>>(); int max=0; for(int i=0;i<dictionary.length;i++) { if(map.containsKey(dictionary[i].length())) { map.get(dictionary[i].length()).add(dictionary[i]); } else { ArrayList<String> arr=new ArrayList<String>(); arr.add(dictionary[i]); map.put(dictionary[i].length(),arr); } max=Math.max(dictionary[i].length(),max); } return map.get(max); } };
原文：http://www.cnblogs.com/kittyamin/p/4990422.html