免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 4547 | 回复: 23

一个字符串匹配的题目 [复制链接]

论坛徽章:
0
发表于 2013-03-10 18:26 |显示全部楼层
本帖最后由 kk861123 于 2013-03-12 10:58 编辑

无意中翻到2gua的博客,看到这个题目:
看到一个据说是腾讯面试时有关一个字符串比较的题:

假设两个字符串中所含有的字符和个数都相同我们就叫这两个字符串匹配,比如:abcda和adabc,由于出现的字符个数都是相同,只是顺序不同,所以这两个字符串是匹配的。要求高效!

这是python的解决方案:http://blog.chinaunix.net/uid-16111523-id-3345463.html 说白了就是排序,sorted的方法,用perl来做的方法大约为:
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4. use Data::Dumper;
  5. use 5.012;

  6. my $str1 = 'abcda';
  7. my $str2 = 'adabc';
  8. my @x = sort2array($str1);
  9. my @y = sort2array($str2);

  10. if ( @x ~~ @y ) {
  11.     print "Y\n";
  12. } else {
  13.     print "N\n";
  14. }
  15. sub sort2array { return sort(split //,$_[0]) }
复制代码
不过接着就有人质疑,如果字符串很长的情况下使用排序就不是什么好方法了,2gua给出的Counter用法,和perl的hash计算后再比较kv值如出一辙,且发现一个关于hash中数据存放的问题,请能给解释下?
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4. use Data::Dumper;

  5. my $str1 = 'abcda';
  6. my $str2 = 'adabc';

  7. my (%m,%n);
  8. $m{$_}++ for split //,$str1;
  9. $n{$_}++ for split //,$str2;

  10. # 为什么两个hash的数据存放顺序是一致的?我说的对吗?谁给解释下?
  11. my @counter1 = hash2array(\%m);
  12. my @counter2 = hash2array(\%n);
  13. print "@counter1\n";
  14. print "@counter2\n";

  15. if ( @counter1 ~~ @counter2 ) {
  16.     print "Y\n";
  17. }

  18. # 转为数组进行智能匹配
  19. sub hash2array { return %{$_[0]} }
复制代码
另外,还想了一种方法用正则来处理,也请大家一起看看哪种效率会高点?
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4. use Data::Dumper;

  5. my $str1 = 'abcda';
  6. my $str2 = 'adabc';

  7. print newMatch($str1,$str2), "\n";

  8. sub newMatch{
  9.     my ($str1, $str2) = @_;
  10.     return 'N' if length($str1) != length($str2);
  11.     my $is_match = 'Y';
  12.     while ( $str1 =~ s/.// ) {
  13.         unless ( $str2 =~ s/$&// ) {
  14.             $is_match = 'N';
  15.         }
  16.     }
  17.     return $is_match;
  18. }
复制代码

论坛徽章:
2
射手座
日期:2014-10-10 15:59:4715-16赛季CBA联赛之上海
日期:2016-03-03 10:27:14
发表于 2013-03-10 19:54 |显示全部楼层
本帖最后由 yinyuemi 于 2013-03-10 19:55 编辑

回复 1# kk861123

---

论坛徽章:
2
射手座
日期:2014-10-10 15:59:4715-16赛季CBA联赛之上海
日期:2016-03-03 10:27:14
发表于 2013-03-10 19:54 |显示全部楼层
本帖最后由 yinyuemi 于 2013-03-10 19:56 编辑

回复 1# kk861123


    第一个perl似乎有些问题,print hash2array(\%m) 的结果 并不是用于 后面smart match部分的值。
   比如
   my $str1 = 'abcda';
    my $str2 = 'adabc3';
    执行结果是Y

   第二个的perl可以提高下效率(最坏的情况是两个字符串很长很长,而且相同),如下
  1. sub newMatch{
  2.     my ($str1, $str2) = @_;
  3.     return 'N' if length($str1) ne length($str2);
  4.     while ( $str1 =~ s/.//,$str2=~s/$&// ) {
  5.     }
  6.     return length($str2) ? 'N' : 'Y';
  7. }
复制代码

论坛徽章:
0
发表于 2013-03-10 21:31 |显示全部楼层
回复 3# yinyuemi


    谢谢指正,已修改!您说的是第三个,用正则处理的效率好?我觉得用hash处理的效率会好点,只是不确定hash存储的方式不是无序吗?为什么没有任何处理过的两个hash转成数组后,数据顺序一样呢?难道也有规律?

论坛徽章:
2
射手座
日期:2014-10-10 15:59:4715-16赛季CBA联赛之上海
日期:2016-03-03 10:27:14
发表于 2013-03-10 22:01 |显示全部楼层
回复 4# kk861123


    http://perldoc.perl.org/perlrun.html#PERL_HASH_SEED

   正则和hash两种相比的话,有些情况下正则可能很快很快,比如字符1是'abcd' x 10000, 字符2 是'bca' x 10000的情况,不过,我觉得综合考虑应该还是hash要快些

论坛徽章:
46
15-16赛季CBA联赛之四川
日期:2018-03-27 11:59:132015年亚洲杯之沙特阿拉伯
日期:2015-04-11 17:31:45天蝎座
日期:2015-03-25 16:56:49双鱼座
日期:2015-03-25 16:56:30摩羯座
日期:2015-03-25 16:56:09巳蛇
日期:2015-03-25 16:55:30卯兔
日期:2015-03-25 16:54:29子鼠
日期:2015-03-25 16:53:59申猴
日期:2015-03-25 16:53:29寅虎
日期:2015-03-25 16:52:29羊年新春福章
日期:2015-03-25 16:51:212015亚冠之布里斯班狮吼
日期:2015-07-13 10:44:56
发表于 2013-03-11 09:06 |显示全部楼层
回复 4# kk861123


    这个顺序是由 hash 算法和 hash 当前的槽数决定的,只要这两个一样顺序是没问题的,hash 算法在同一个线程是必定一样的,而槽数由和 Perl 的实现密切相关,只在这里这个特定情况下成立。

比如  %h = (a=>,b=1,c=>1); %j = 'a'..'z'; %j=(); %j = (a=>1, b=>1, c=>1); 在我这里顺序就不一样了,因为 %j 的槽数要多过 %h

论坛徽章:
0
发表于 2013-03-11 10:34 |显示全部楼层
回复 5# yinyuemi


    谢谢,有点深啊

论坛徽章:
0
发表于 2013-03-11 10:39 |显示全部楼层
本帖最后由 kk861123 于 2013-03-11 10:45 编辑

回复 6# zhlong8


    谢谢版主解释,清晰了许多!安全期间,还是排序为妙:
  1. #!/usr/bin/perl
  2. use strict;
  3. use warnings;
  4. use Data::Dumper;

  5. my $str1 = 'abcda';
  6. my $str2 = 'adabc';

  7. my (%m,%n);
  8. $m{$_}++ for split //,$str1;
  9. $n{$_}++ for split //,$str2;

  10. # 为什么两个hash的数据存放顺序是一致的?我说的对吗?谁给解释下?
  11. my @counter1 = hash2sortedarray(\%m);
  12. my @counter2 = hash2sortedarray(\%n);
  13. print "@counter1\n";
  14. print "@counter2\n";

  15. if ( @counter1 ~~ @counter2 ) {
  16.     print "Y\n";
  17. }

  18. # 转为数组进行智能匹配
  19. sub hash2array { return %{$_[0]} }
  20. sub hash2sortedarray { return map { $_ => $_[0]->{$_} } sort keys %{$_[0]} }
复制代码

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2013-03-11 10:47 |显示全部楼层
谢谢啊{:3_188:}

论坛徽章:
3
CU十二周年纪念徽章
日期:2013-10-24 15:41:34子鼠
日期:2013-12-14 14:57:19射手座
日期:2014-04-25 21:23:23
发表于 2013-03-11 11:01 |显示全部楼层
学习了~~~{:3_190:}   
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP