[已解决]成长每一点---题库09---5 Kuy（难度---字符串处理）

Stubborn

完成scramble(s1,s2)这个函数，（s1和s2参数为字符串形式）使其：

1、当s1经过排序后（实际上不排序也可以）可以被s2匹配到，匹配到返回True，匹配不到返回False。

2、s1、s2字符串只考虑a到z小写的情况，不考虑包含任何数字和标点等情况。

3、s1和s2可以有重复,例如两个a匹配两个a（'scriptjava'和'javascript'。）

4、要考虑到性能性，时间规定不能运行超过1秒2。(后面会随机测试到80万位字母)




最开始我用for循环去历遍判断，代码如下：

1. def scramble(s1, s2):
   
2.     s1 = list(s1)
   
3.     for each in s2:
   
4.         if each in s1:
   
5.             s1.remove(each)
   
6.         else:
   
7.             return False
   
8.     return True

复制代码

代码测试的时候提示超时：执行超时（12000毫秒），估摸着是算法问题，没有优化，可能计算会是一个很大很长的字符串
在后面我改用模块collections，直接比对他们字母的个数，已经把循环压缩到最多26次了。有什么地方会对运算产生比较长的运算时间消耗？代码是这样的：

1. import collections
   
2. def scramble(s1, s2):
   
3.     cont = 0
   
4.     temp = set(s2)
   
5.     for each in temp:
   
6.         if collections.Counter(s1)[each]<collections.Counter(s2)[each]:
   
7.             return False
   
8.         else:
   
9.             cont += 1
   
10.     if cont == len(temp):
    
11.         return True

复制代码

还是会有执行超时Execution Timed Out (12000 ms)
有没有有木有其他的算法，或者思路？

最佳答案

月排行榜 / 总排行榜

heidern0612

2019-1-9 11:59:50

1. from collections import Counter
   
2. 
   
3. def scramble(s1,s2):
   
4.     return len(Counter(s2)-Counter(s1)) == 0

复制代码

跳转到最佳答案楼层

Stubborn

@塔利班 @heidern0612 还是这个网站坑爹？

塔利班

网站一般不会坑，只是你的代码没有考虑复杂度，人家要求严格，我也没看懂你的题目是啥，难道这个网站题目都是描述不清楚的么

heidern0612

1. from collections import Counter
   
2. 
   
3. def scramble(s1,s2):
   
4.     return len(Counter(s2)-Counter(s1)) == 0

复制代码

heidern0612

给个地址：戳我前进

原题的意思是：

完成scramble(s1,s2)这个函数，（s1和s2参数为字符串形式）使其：

[b]1、当s1经过排序后（实际上不排序也可以）可以被s2匹配到，匹配到返回True，匹配不到返回False。

2、s1、s2字符串只考虑a到z小写的情况，不考虑包含任何数字和标点等情况。

3、s1和s2可以有重复,例如两个a匹配两个a（'scriptjava'和'javascript'。）

4、要考虑到性能性，时间规定不能运行超过1秒2。(后面会随机测试到80万位字母)[/b]



例子如下：

1. Test.assert_equals(scramble('rkqodlw', 'world'),  True)
   
2. Test.assert_equals(scramble('cedewaraaossoqqyt', 'codewars'), True)
   
3. Test.assert_equals(scramble('katas', 'steak'), False)
   
4. Test.assert_equals(scramble('scriptjava', 'javascript'), True)
   
5. Test.assert_equals(scramble('scriptingjava', 'javascript'), True)

复制代码

P.S：我感觉这个给冬雪雪冬版主推荐下不错，不知道大神还有没有别的办法，求科普一波。


@塔利班  @冬雪雪冬  @Stubborn

塔利班

heidern0612 发表于 2019-1-9 11:59

你这个代码对吗，，

heidern0612

塔利班 发表于 2019-1-9 14:43
你这个代码对吗，，

对

塔利班

1. def scramble(s1, s2):
   
2.     d=set()
   
3.     for e in s2:
   
4.         if s2.count(e)>s1.count(e):
   
5.             return False
   
6.         d.add(e)
   
7.         if len(d)==26:
   
8.             break
   
9.     return True

复制代码

写了个勉强通过的

heidern0612

塔利班 发表于 2019-1-9 14:53
写了个勉强通过的

他这个提交后，会有好几种别人的解法。

大神你这个解法跟我一开始想的差不多，不过我没考虑重复情况，我只考虑出现情况了。

测试到80万字符就出错。

Stubborn

heidern0612 发表于 2019-1-9 11:59

惭愧惭愧