文档章节

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

大数据之路
 大数据之路
发布于 2012/09/16 00:33
字数 411
阅读 606
收藏 7

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

最新九月百度人搜,阿里巴巴,腾讯华为京东小米笔试面试二十题

http://blog.csdn.net/v_july_v/article/details/7974418 

精选30道Java笔试题解答

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

 

© 著作权归作者所有

共有 人打赏支持
大数据之路
粉丝 1542
博文 516
码字总数 343694
作品 0
武汉
架构师
私信 提问
加载中

评论(2)

刘毕维
代码是简洁,但需要是高效,应当分析执行时间。
江斌
江斌
这题ascii就每没啥好说了
微软等公司数据结构+算法面试100题

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / / 6 14 / / / / 4 ...

chambai
2012/08/05
0
0
一道ISCC题引申的PHP正则复习

iscc中的一道web题“试试看”,描述为随意开火 起初看url,以为是一道常规的文件包含题,后面试了很多方法都出不来 最后受到其他师傅的启发才得到payload 这里有两种payload都可以 (PHP 4, ...

日生三金
05/15
0
0
2018 前端面试准备

前端面试常见问题按知识点分类整理 前端面试常考问题整理,按模块知识点分类,持续完善中... Front-end-Developer-Questions by Modules and knowledge 前端面试经典问题:CSS 中居中的几种方...

掘金官方
2017/12/14
0
0
出来混总是要还的-JS正则前传

前言: 正则表达式一直是个人痛点, 相信很多人 ( 说的就是你 ) 跟我一样存在类似的情况, 正则是反复学, 反复忘, 从个人角度看主要的原因还是:较少的使用场景, 如果像数组的几个常用方法一样,...

ntscshen
10/17
0
0
各大公司(Google,Microsoft,Baidu, Microsoft Research Asia etc.)实习生面试题总汇

1.把二元查找树转变成排序的双向链表(树) 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / 6 14 / / 4 8 12 1...

云栖希望。
2017/12/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

容器之Zookeeper的使用

我们使用zookeeper时,都是在Linux上安装zookeeper,之后启动时要加入配置文件。 使用docker之后,我们可以直接使用镜像运行容器,镜像可以从docker.hub上下载,地址是https://hub.docker.co...

克虏伯
18分钟前
0
0
esxi 更换ssl证书

概述 就是想换一个证书而已,你可以通过下面的途径去申请一个泛解析域名的证书之后再esxi上安装上 使用阿里云域名api申请Let’s Encrypt泛域名免费ssl证书 申请完成证书之后进行下一步 操作 ...

bboysoulcn
31分钟前
1
0
PLC编程入门:梯形图

梯形图(LAD)是PLC编程的最佳可视化语言,它看起来非常类似于继电器电路图,因此如果 你对继电器控制和电子电路有所了解的话,那么学起来会非常容易! 在这个教程中,我们将学习关于使用梯形...

汇智网教程
34分钟前
1
0
Kubernetes 1.13.0的快速升级

Kubernetes 1.13.0已经正式发布,快速升级(含国内镜像快速下载链接)包括升级kubeadm/kubectl/kubelet版本、拉取镜像、升级Kubernetes集群三个主要步骤。注意Kubernetes 1.13.0版本暂时不支...

openthings
47分钟前
2
0
go的卸载和环境变量配个人.bashrc

若是用安装包直接解压 http://download.csdn.net/detail/u010026901/7592581 cd /usr/local tar -zxvf go1.1.2.linux-386.tar.gz(先把安装包移到这个目录) 3.安装 $ cd go/src,$ ./all.b......

dragon_tech
53分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部