lintcode 乱序字符串 python

原题是这样的:

给出一个字符串数组S,找到其中所有的乱序字符串(Anagram)。如果一个字符串是乱序字符串,那么他存在一个字母集合相同,但顺序不同的字符串也在S中。

样例

对于字符串数组["lint","intl","inlt","code"]

返回["lint","inlt","intl"]

刚开始的想法是,使用dict字典才记录,字母,可是这样会需要很多的字典,并且处理起来不方便。后来就想到了给字符排序

原理很简单,给上面的字符排序,就像西面的这个过程

s = "adceb"
 l = list(s)
 l.sort()
 s1 = "".join(l)

通过这一步的处理之后,可以看到s1为 "abcde"

那么我们对传进来的数组中的所有元素,进行这个排序。因为我们按照特定的排序方式进行排序,必然会导致一样的排序结果。那么只要排序后的字符串是一致的,那么我们就可以肯定这几个字符串是相同的字符串

那么,下面直接上代码

class Solution:
     """
     @param: strs: A list of strings
     @return: A list of strings
     """
     def anagrams(self, strs):
         # write your code here
         if strs == None and strs == []:
             return strs
         if len(strs) == 1:
             return strs
             
         returnlist = []
         templist = {}
         for i in range(len(strs)):
             if strs[i] == None and strs[i] == "":
                 continue
             s = strs[i]
             s1="".join((lambda x:(x.sort(),x)[1])(list(s))) #这一句是百度出来的,但是也不难理解,将s的list传入,排序后,返回x
             if s1 in templist:
                 templist[s1].append(i)
             if s1 not in templist:
                 templist[s1] = [i]
                 
         for k in templist.keys():
             if len(templist.get(k)) > 1:
                 for i in templist.get(k):
                     returnlist.append(strs[i])
         return returnlist

ok done,如果有更好的算法,也请分享给我。谢谢!

相关推荐