[PISNアルゴリズムインタビュー]文字列アクション-グループアニメーション

파이썬 알고리즘 인터뷰という本を読みましたが、草だけを読むよりも、それをめちゃくちゃにしてから草を読んだほうがいいです.

🐍 質問する

文字列配列を受け入れ、アンナック単位でグループ化します.

アンナック:文字を並べ直して、他の意味の単語に変えます 例文と「門前朴大->大発専門家」、翻訳メモリ

入力

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

出力
[ ["ate", "eat", "tea"], ["nat", "tan"], ["bat"] ]

🐍 説明する

最後に、同じ文字が使用されていることを利用して、文字列を並べ替えた後、並べ替えられた文字列と同じか否かでアクセントが付けられるか否かを判断する.同じ文字リストで、必要な出力形式で整理しました.出力リストに個別にソートする条件がないので、そのまま出力しました.

input_list = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']

# 입력받은 문자열을 sorted함수를 이용해 정렬
input_dict = dict()
for string in input_list:
	input_dict[string] = "".join(sorted(string))
# input_dict : {'eat': 'aet', 'tea': 'aet', 'tan': 'ant', 'ate': 'aet', 'nat': 'ant', 'bat': 'abt'}
    
output_dict = dict()
for ori_string, sort_string in input_dict.items():
	if sort_string in output_dict.keys():
		output_dict[sort_string].append(ori_string)
	else:
		output_dict[sort_string] = [ori_string]
# output_dict : {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

answer = list(output_dict.values())
# answer : [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

🐍 教材の解釈

同じ方法ですが、コードはもっと簡潔です.バイナリ単位のバイナリコードに文字列を挿入する際にキー値が存在するか否かを判断するプロセスを減らすためにcollectionsのdefaultdictを用いた.defaultdictを使用すると、for文を1つ減らすことができます.

import collections

def groupAnagrams(strs):
	anagrams = collections.defaultdict(list)
	for word in strs:
		anagrams[''.join(sorted(word))].append(word)
	return list(anagrams.values())
    
input_list = ['eat', 'tea', 'tan', 'ate', 'nat', 'bat']
groupAnagrams(input_list)
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]