Chinaunix首页 | 论坛 | 博客
  • 博客访问: 619384
  • 博文数量: 233
  • 博客积分: 2221
  • 博客等级: 大尉
  • 技术积分: 3184
  • 用 户 组: 普通用户
  • 注册时间: 2010-02-16 14:01
个人简介

瓜瓜派的瓜瓜

文章分类

全部博文(233)

文章存档

2013年(28)

2012年(197)

2011年(8)

分类: Python/Ruby

2012-09-12 11:14:02

看到一个据说是腾讯面试时有关一个字符串比较的题:
假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,所以这两个字符串是匹配的。要求高效!

当然考虑用高效快捷的Python来练一练,看到有人很快就写下了以下代码:
>>> sorted('abcda') == sorted('adabc')
True

Geek的玩法很多,除了有人先提到的上面做法,我还想到以下方法也挺Geek:
>>> from collections import Counter
>>> Counter('abcda') == Counter('adabc')
True
Counter类在Python 2.7里被新增进来

看看结果,是一样的:
>>> Counter('abcda')
Counter({'a': 2, 'c': 1, 'b': 1, 'd': 1})
>>> Counter('adabc')
Counter({'a': 2, 'c': 1, 'b': 1, 'd': 1})

另外,可以稍微格式化输出结果看看,用到了Counter类的elements()方法:
>>> list(Counter('abcda').elements())
['a', 'a', 'c', 'b', 'd']
>>> list(Counter('adabc').elements())
['a', 'a', 'c', 'b', 'd']

谁说Python只有一种方式?现在的Python在保持简捷高效的一贯风格的同时,玩法也越来越多了。

阅读(1518) | 评论(3) | 转发(0) |
给主人留下些什么吧!~~

lmnos2012-09-30 00:53:21

Bean_lee: 如果两个字符串的长度分别是M,和N的话,排序不是个好办法,想想如果M=1000万,N=1000万。

字符,能打印也好,不能打印也好,一共就有256个,开个256的数组,遍.....
呵呵 你对各种算法很有研究的嘛

Bean_lee2012-09-29 21:57:52

呵呵,看来你也是这么玩的,字符串匹配,是算法里面一个派别吧。当年我面试的时候,也问我这个问题了,我当时太死板,不能灵活应用学到的东西。

Bean_lee2012-09-29 21:55:05

如果两个字符串的长度分别是M,和N的话,排序不是个好办法,想想如果M=1000万,N=1000万。

字符,能打印也好,不能打印也好,一共就有256个,开个256的数组,遍历两个字符串,每个字符出现,则在对应的数组位置+1,就能统计出256个字符各个字符出
现的次数,然后比较两个数组就好了。

复杂度O(M+N)