LeetCode: Anagrams 解题报告-白红宇

LeetCode: Anagrams 解题报告

阅读量：5280 次

发布时间：2019-06-14

本文共 2841 字，大约阅读时间需要 9 分钟。

Anagrams

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

思路：

建Hashtable，用排序过的string作为key，它的anagram作为ArrayList

这道题之前用暴力写的O(N^2)的TLE了，改用Hashtable来写

题目的意思是给一个String数组，找出其中由相同字母组成的单词。

例如：

S = ["abc", "bca", "bac", "bbb", "bbca", "abcb"]

答案为：

["abc", "bca", "bac", "bbca", "abcb"]

只有"bbb"没有相同字母组成的单词。

ref: http://blog.csdn.net/fightforyourdream/article/details/14217985

1 public class Solution { 2     public List
      
        anagrams(String[] strs) { 3         List
       
         ret = new ArrayList
        
         (); 4          5         if (strs == null) { 6             return ret; 7         } 8          9         HashMap
         
          > map = new HashMap
          
           >();10         11         int len = strs.length;12         for (int i = 0; i < len; i++) {13             String s = strs[i];14             15             // Sort the string.            16             char[] chars = s.toCharArray();17             Arrays.sort(chars);18             String strSort = new String(chars);   19             20             // Create a ArrayList for the sorted string.            21             if (!map.containsKey(strSort)) {22                 map.put(strSort, new ArrayList
           
            ());23 }24 25 // Add a new string to the list of the hashmap.26 map.get(strSort).add(s);27 }28 29 // go through the map and add all the strings into the result.30 for (Map.Entry
            
             > entry: map.entrySet()) {31 List
             
               list = entry.getValue();32 33 // skip the entries which only have one string.34 if (list.size() == 1) {35 continue;36 }37 38 // add the strings into the list.39 ret.addAll(list);40 }41 42 return ret;43 }44 }

View Code

2015.1.3 redo:

1 public class Solution { 2     public List
      
        anagrams(String[] strs) { 3         List
       
         ret = new ArrayList
        
         (); 4         if (strs == null) { 5             return ret; 6         } 7          8         HashMap
         
          > map = new HashMap
          
           >(); 9         for (int i = 0; i < strs.length; i++) {10             String s = strs[i];11             char[] chars = s.toCharArray();12             13             Arrays.sort(chars);14             String sSort = new String(chars);15             16             if (map.containsKey(sSort)) {17                 map.get(sSort).add(s);18             } else {19                 List
           
             list = new ArrayList
            
             ();20 list.add(s);21 map.put(sSort, list);22 }23 }24 25 // Bug 1: should use map.entrySet() instead of MAP.26 for (Map.Entry
             
              > entry: map.entrySet()) {27 List
              
                list = entry.getValue();28 if (list.size() > 1) {29 ret.addAll(list);30 }31 }32 33 return ret;34 }35 }