python|【leetCode一起来涮题】49. 字母异位词分组 python|面试准备

字母异位词分组给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:
输入: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”] 输出: [
[“ate”,“eat”,“tea”], [“nat”,“tan”], [“bat”] ] 说明：
所有输入均为小写字母。不考虑答案输出的顺序。

【python|【leetCode一起来涮题】49. 字母异位词分组】总结一个万能的题解
按照固定逻辑进行搜索解题
暴力解法：
建立一个桶查找，O(n^2)
根据字符的asc 建立一个表，加法乘法交换律，加起来，
【1+2+9】【4+2+2】
因子相同【129】【361】
长度相等，361*1
方法一：排序数组分类

文章图片

import collections class Solution(object): def groupAnagrams(self, strs): """ :type strs: List[str] :rtype: List[List[str]] collections.defaultdict(list)可以很容易将键-值对序列转换为列表字典 """ ans=collections.defaultdict(list) for s in strs: ans[tuple(sorted(s))].append(s) return list(ans.values())

/** List new ArrayList() Map new HashMap() s.toCharArray() Arrays.sort() String.valueOf() containKey() ans.put(key,value) ans.get(key).add(s) */ class Solution { public List> groupAnagrams(String[] strs) { if (strs.length == 0) return new ArrayList(); Map, List> ans = new HashMap, List>(); for (String s : strs) { char[] ca = s.toCharArray(); Arrays.sort(ca); String key = String.valueOf(ca); if (!ans.containsKey(key)) ans.put(key, new ArrayList()); ans.get(key).add(s); } return new ArrayList(ans.values()); } }

方法二：按计数分类

文章图片

class Solution: def groupAnagrams(strs): ans = collections.defaultdict(list) for s in strs: count = [0] * 26 for c in s: count[ord(c) - ord('a')] += 1 ans[tuple(count)].append(s) return ans.values()

/* strs,length int[] count = new int[26] Arrays.fill(count,0)*/ class Solution { public List> groupAnagrams(String[] strs) { if (strs.length == 0) return new ArrayList(); Map, List> ans = new HashMap, List>(); int[] count = new int[26]; for (String s : strs) { Arrays.fill(count, 0); for (char c : s.toCharArray()) count[c - 'a']++; StringBuilder sb = new StringBuilder(""); for (int i = 0; i < 26; i++) { sb.append('#'); sb.append(count[i]); } String key = sb.toString(); if (!ans.containsKey(key)) ans.put(key, new ArrayList()); ans.get(key).add(s); } return new ArrayList(ans.values()); } }作者：LeetCode 链接：https://leetcode-cn.com/problems/group-anagrams/solution/zi-mu-yi-wei-ci-fen-zu-by-leetcode/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

String、StringBuffer和StringBuilder的区别