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,如果有更好的算法,也请分享给我。谢谢!
相关推荐
xiaoseyihe 2020-08-11
pythonxuexi 2020-07-30
leoaran 2020-07-21
littie 2020-07-19
zcabcd 2020-07-18
yjsflxiang 2020-07-04
liusarazhang 2020-06-28
银角大王 2020-06-25
leoaran 2020-06-22
Lexan 2020-06-15
liusarazhang 2020-06-14
89411051 2020-06-14
chinademon 2020-06-11
leoaran 2020-06-06
tengyuan 2020-06-03
shengnanonly 2020-06-03
joyjoy0 2020-06-02