首页 > 代码库 > LeetCode: Anagrams 解题报告
LeetCode: Anagrams 解题报告
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<String> anagrams(String[] strs) { 3 List<String> ret = new ArrayList<String>(); 4 5 if (strs == null) { 6 return ret; 7 } 8 9 HashMap<String, List<String>> map = new HashMap<String, List<String>>();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<String>());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<String, List<String>> entry: map.entrySet()) {31 List<String> 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 }
https://github.com/yuzhangcmu/LeetCode_algorithm/blob/master/hash/Anagrams.java
LeetCode: Anagrams 解题报告
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。