leetcode 49. 字母异位词分组

字母异位词分组

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

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

解题思路：
想法很简单，异位词可以直接用set来判断，但是set判断实在是消耗资源，所以我的想法就是自己写一个类hash函数来代替set，因为异位词都是小写字母，所以可以用一个26位长的数组来表示所有的异位词，数组的每个index对应相应字母的个数（’a’:0等等)，然后这个数组转为字符串就是这些异位词的类hashcode啦

代码

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        res = []
        if not strs:
            return res
        if len(strs) == 1:
            return [strs]
        temp_dict = dict(zip(map(chr,range(97,123)), range(26)))
        temp_table = dict()
        def self_hash(string_candidate, temp_dict):
            temp = [0 for _ in xrange(26)]
            if not string_candidate:
                return ''.join(map(str,temp))
            for i in string_candidate:
                idx = temp_dict[i]
                temp[idx] += 1
            return ''.join(map(str, temp))
        for s in strs:
            hash_code = self_hash(s, temp_dict)
            if temp_table.get(hash_code) is None:
                temp_table[hash_code] = []
            temp_table[hash_code].append(s)
        return temp_table.values()