变位词排序

题目

请编写一个方法，对一个字符串数组进行排序，将所有变位词合并，保留其字典序最小的一个串。这里的变位词指变换其字母顺序所构成的新的词或短语。例如"triangle"和"integral"就是变位词。

给定一个string的数组str和数组大小int n，请返回排序合并后的数组。保证字符串串长小于等于20，数组大小小于等于300。

测试样例： [“ab”,“ba”,“abc”,“cba”] 返回：[“ab”,“abc”]

思路

先对列表里的字符串排序，然后在判断排序后的字符串是否在字典里，不在就加到字典里，key为排序后，value为排序前状态，如果后面的字符串在dict里，则要比较他们的字典序，如果小，就替换。最后返回的时排序前的字符串并做一次排序。

代码

class SortString: def sortStrings(self, s, n): dict = {} ss = [] for i in range(n): newstr = ''.join(sorted(s[i])) if newstr not in dict: dict[newstr] = s[i] elif dict[newstr]>s[i]: dict[newstr] = s[i] for key in dict: ss.append(dict[key]) ss.sort() return ss