专栏首页数据之美关于腾讯的一道字符串匹配的面试题

关于腾讯的一道字符串匹配的面试题

Question:

 假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,

 比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,

 所以这两个字符串是匹配的。要求高效!

Answer:

假定字符串中都是ASCII字符。如下用一个数组来计数,前者加,后者减,全部为0则匹配。

static bool IsMatch(string s1, string s2)
        {
            if (s1 == null && s2 == null) return true;
            if (s1 == null || s2 == null) return false;

            if (s1.Length != s2.Length) return false;

            int[] check = new int[128];

            foreach (char c in s1)
            {
                check[(int)c]++;
            }
            foreach (char c in s2)
            {
                check[(int)c]--;
            }
            foreach (int i in check)
            {
                if (i != 0) return false;
            }

            return true;
        }

如果使用python的话,就更简单了:

  1. >>> sorted('abcda') == sorted('adabc')
  2. True

复制代码Geek的玩法很多,除了有人先提到的上面做法,我还想到以下方法也挺Geek:

  1. >>> from collections import Counter
  2. >>> Counter('abcda') == Counter('adabc')
  3. True

复制代码 (Counter类在Python 2.7里被新增进来) 看看结果,是一样的:

  1. >>> Counter('abcda')
  2. Counter({'a': 2, 'c': 1, 'b': 1, 'd': 1})
  3. >>> Counter('adabc')
  4. Counter({'a': 2, 'c': 1, 'b': 1, 'd': 1})

复制代码 另外,可以稍微格式化输出结果看看,用到了Counter类的elements()方法:

  1. >>> list(Counter('abcda').elements())
  2. ['a', 'a', 'c', 'b', 'd']
  3. >>> list(Counter('adabc').elements())
  4. ['a', 'a', 'c', 'b', 'd']

复制代码

REF:

http://blog.sina.com.cn/s/blog_5fe9373101011pj0.html

http://bbs.chinaunix.net/thread-3770641-1-1.html

http://topic.csdn.net/u/20120908/21/F8BE391F-E4F1-46E9-949D-D9A640E4EE32.html

精选30道Java笔试题解答

http://www.cnblogs.com/lanxuezaipiao/p/3371224.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 摩拜单车爬虫源码及解析

    專 欄 ❈我是思聪,Python中文社区专栏作者 博客: http://www.jianshu.com/u/b1e713e56ea6❈ 为什么爬摩拜的数据 ...

    Python中文社区
  • 雪球网沪深全站股票评论爬虫

    專 欄 ❈ 蜗牛仔,Python中文社区专栏作者,怒学Python爬虫,争当爬虫工程师, github地址: https://github.com/xiaob...

    Python中文社区
  • 用Python玩转微信的正确姿势!

    0. itchat 最近研究了一些微信的玩法,我们可以通过网页版的微信微信网页版,扫码登录后去抓包爬取信息,还可以post去发送信息。 然后发现了itchat这...

    Python中文社区
  • 如何构建一个分布式爬虫(理论篇)

    專 欄 ❈resolvewang,Python中文社区专栏作者 Python和Go爱好者。具有较为丰富的爬虫和反爬虫经验,对web编程略知一二,对基础架构比较感...

    Python中文社区
  • Python微型Web框架Bottle源码分析

    專 欄 ❈正小歪,Python 工程师,主要负责 Web 开发和日志数据处理。博客文章《真正的 Tornado 异步非阻塞》、《使用 JWT 让你的 RESTf...

    Python中文社区
  • ALI的Tensorflow炼成与GAN科普

    專 欄 ❈那只猫,Python中文社区专栏作者,Python中文社区新Logo设计人,纯种非CS科班数据分析人,沉迷Keras。在Cambridge做了点小事...

    Python中文社区
  • 用Python搭建一个校园维基网站(一)

    專 欄 ❈ treelake ,Python中文社区专栏作者 项目Github地址: https://github.com/zr777/school-wik...

    Python中文社区
  • 用python搭建一个校园维基网站(二)—— 可编辑内容的首页的创建

    專 欄 ❈ treelake ,Python中文社区专栏作者 项目Github地址: https://github.com/zr777/school-wik...

    Python中文社区
  • 如何使用爬虫分析Python岗位招聘情况

    專 欄 ❈陈键冬,Python中文社区专栏作者 GitHub: https://github.com/chenjiandongx ❈ Life is short...

    Python中文社区
  • GayHub用户及仓库分析爬虫

    專 欄 ❈陈键冬,Python中文社区专栏作者 GitHub: https://github.com/chenjiandongx ❈ 爬虫介绍 Github ...

    Python中文社区

扫码关注云+社区

领取腾讯云代金券