LeetCode中級アルゴリズム(配列と文字列)-ワードパズルグループ

ワードパズルグループ
文字列配列を指定し、アルファベット異位語を組み合わせます.アルファベット異位語とは、アルファベットは同じですが、異なる文字列を並べます.
例:

  : ["eat", "tea", "tan", "ate", "nat", "bat"],
  :
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

説明:

          。
          。

Python:
第1回解法:タイムアウト

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        result = []
        letter_list = []
        temp_list = []

        str_myset = set(strs)
        if len(set(strs)) == 1:
            for value in strs:
                letter_list.append(value)
            result.append(letter_list)
            return result
        for w in range(ord("a"),ord("z") + 1):
            letter_list.append(chr(w))
        
        res = []
        dic_set = []
        for str_value in strs:
            dic_val = {}
            if str_value == "":
                temp_list.append(str_value)
                pass

            for char in str_value:
                if char in dic_val:
                    dic_val[char] +=1
                else:
                    dic_val[char] = 1
            if dic_val not in res and len(dic_val) > 0:
                dic_set.append(dic_val)
            res.append(dic_val)

        for value in dic_set:
            lis_a = []
            for idx in range(len(res)):
                if value == res[idx]:
                    lis_a.append(strs[idx])
                pass
            result.append(lis_a)
        if len(temp_list) > 0:
            result.append(temp_list)
        return result

最適化後の:それともタイムアウト!!?

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        length_d = len(strs)
        sorted_list = []
        res = []
        for i in range(length_d):
            if sorted(strs[i]) not in sorted_list:
                sorted_list.append(sorted(strs[i]))
        for value in sorted_list:
            list_a = []
            for i in range(length_d):
                if value == sorted(strs[i]):
                    list_a.append(strs[i])
            res.append(list_a)
        return res

再最適化:

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        length_d = len(strs)
        sorted_list = []
        res = []
        for i in range(length_d):
            lis_a = []
            if sorted(strs[i]) not in sorted_list:
                sorted_list.append(sorted(strs[i]))
            index = sorted_list.index(sorted(strs[i]))
            if len(res) > index:
                res[index].append(strs[i])
                pass
            else:
                lis_a.append(strs[i])
                res.append(lis_a)
        return res

??どうにか
また、また..二次最適化:

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        res = {}
        for value in strs:
            list_a = []
            char = "".join(sorted(value))
            if char not in res:
                list_a.append(value)
                res[char] = list_a
            else:
                res[char].append(value)
        # print(res)
        return res.values()

次は大物です:1:

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        hash = {}
        for str in strs:
            char = ''.join(sorted(str))
            if char not in hash:
                hash[char] = [str]
            else:
                hash[char].append(str)
                
        return hash.values()

2:

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        dic = dict()
        result = []
        classnum = 0
        
        for item in strs:
            l = list(item)
            l.sort()
            string = str(l)
            if dic.has_key(string):
                result[dic[string]].append(item)
            else:
                dic[string] = classnum
                result.append([item])
                classnum += 1
                
        return result