首页 > > 网络编程 > 其它 >

lintcode 乱序字符串 python

2018-06-18 00:05:52来源：未知阅读 ()

原题是这样的：

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

样例

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

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

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

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

1 s = "adceb"
2 l = list(s)
3 l.sort()
4 s1 = "".join(l)

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

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

那么，下面直接上代码

 1 class Solution:
 2     """
 3     @param: strs: A list of strings
 4     @return: A list of strings
 5     """
 6     def anagrams(self, strs):
 7         # write your code here
 8         if strs == None and strs == []:
 9             return strs
10         if len(strs) == 1:
11             return strs
12             
13         returnlist = []
14         templist = {}
15         for i in range(len(strs)):
16             if strs[i] == None and strs[i] == "":
17                 continue
18             s = strs[i]
19             s1="".join((lambda x:(x.sort(),x)[1])(list(s))) #这一句是百度出来的，但是也不难理解，将s的list传入，排序后，返回x
20             if s1 in templist:
21                 templist[s1].append(i)
22             if s1 not in templist:
23                 templist[s1] = [i]
24                 
25         for k in templist.keys():
26             if len(templist.get(k)) > 1:
27                 for i in templist.get(k):
28                     returnlist.append(strs[i])
29         return returnlist