首页 > 代码库 > Group Anagrams Leetcode
Group Anagrams Leetcode
Given an array of strings, group anagrams together.
For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"]
,
Return:
[ ["ate", "eat","tea"], ["nat","tan"], ["bat"] ]
Note: All inputs will be in lower-case.
这个一开始的方法是对的,但是test case只能过98/100个,后面就超时了。。。不过还是放上来以示警戒参考吧。思路和之前的一样。
public class Solution { public List<List<String>> groupAnagrams(String[] strs) { List<List<String>> res = new ArrayList<>(); if (strs == null || strs.length == 0) { return res; } Set<Integer> hs = new HashSet<>(); for (int i = 0; i < strs.length; i++) { if (hs.contains(i)) { continue; } List<String> anagram = new ArrayList<>(); anagram.add(strs[i]); for (int j = i + 1; j < strs.length; j++) { if (hs.contains(j)) { continue; } if (isAnagram(strs[i], strs[j])) { hs.add(j); anagram.add(strs[j]); } } res.add(anagram); } return res; } public boolean isAnagram(String a, String b) { if (a == null && b == null) { return true; } if (a == null || b == null) { return false; } int[] h = new int[26]; for (int i = 0; i < a.length(); i++) { h[a.charAt(i) - ‘a‘]++; } for (int i = 0; i < b.length(); i++) { h[b.charAt(i) - ‘a‘]--; if (h[b.charAt(i) - ‘a‘] < 0) { return false; } } for (int i = 0; i < h.length; i++) { if (h[i] != 0) { return false; } } return true; } }
还可以用排序做,复杂度其实降低了。
看了top solution之后写的。。。高下立现。。。
public class Solution { public List<List<String>> groupAnagrams(String[] strs) { if (strs == null) { return null; } HashMap<String, List<String>> hm = new HashMap<>(); for (int i = 0; i < strs.length; i++) { char[] c = strs[i].toCharArray(); Arrays.sort(c); String str = new String(c); if (hm.containsKey(str)) { hm.get(str).add(strs[i]); } else { List<String> ana = new ArrayList<>(); ana.add(strs[i]); hm.put(str, ana); } } return new ArrayList<List<String>>(hm.values()); } }
又学了一种新的构造函数。。。
Group Anagrams Leetcode
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。