一个字符串匹配的题目

kk861123

无意中翻到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. 
   
7. my $str1 = 'abcda';
   
8. my $str2 = 'adabc';
   
9. my @x = sort2array($str1);
   
10. my @y = sort2array($str2);
    
11. 
    
12. if ( @x ~~ @y ) {
    
13.     print "Y\n";
    
14. } else {
    
15.     print "N\n";
    
16. }
    
17. 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. 
   
6. my $str1 = 'abcda';
   
7. my $str2 = 'adabc';
   
8. 
   
9. my (%m,%n);
   
10. $m{$_}++ for split //,$str1;
    
11. $n{$_}++ for split //,$str2;
    
12. 
    
13. # 为什么两个hash的数据存放顺序是一致的？我说的对吗？谁给解释下？
    
14. my @counter1 = hash2array(\%m);
    
15. my @counter2 = hash2array(\%n);
    
16. print "@counter1\n";
    
17. print "@counter2\n";
    
18. 
    
19. if ( @counter1 ~~ @counter2 ) {
    
20.     print "Y\n";
    
21. }
    
22. 
    
23. # 转为数组进行智能匹配
    
24. sub hash2array { return %{$_[0]} }
    

复制代码

另外，还想了一种方法用正则来处理，也请大家一起看看哪种效率会高点？

1. #!/usr/bin/perl
   
2. use strict;
   
3. use warnings;
   
4. use Data::Dumper;
   
5. 
   
6. my $str1 = 'abcda';
   
7. my $str2 = 'adabc';
   
8. 
   
9. print newMatch($str1,$str2), "\n";
   
10. 
    
11. sub newMatch{
    
12.     my ($str1, $str2) = @_;
    
13.     return 'N' if length($str1) != length($str2);
    
14.     my $is_match = 'Y';
    
15.     while ( $str1 =~ s/.// ) {
    
16.         unless ( $str2 =~ s/$&// ) {
    
17.             $is_match = 'N';
    
18.         }
    
19.     }
    
20.     return $is_match;
    
21. }
    

复制代码

yinyuemi

回复 1# kk861123

---

yinyuemi

回复 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. }

复制代码

kk861123

回复 3# yinyuemi


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

yinyuemi

回复 4# kk861123


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

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

zhlong8

回复 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

kk861123

回复 5# yinyuemi


    谢谢，有点深啊

kk861123

回复 6# zhlong8


    谢谢版主解释，清晰了许多！安全期间，还是排序为妙：

1. #!/usr/bin/perl
   
2. use strict;
   
3. use warnings;
   
4. use Data::Dumper;
   
5. 
   
6. my $str1 = 'abcda';
   
7. my $str2 = 'adabc';
   
8. 
   
9. my (%m,%n);
   
10. $m{$_}++ for split //,$str1;
    
11. $n{$_}++ for split //,$str2;
    
12. 
    
13. # 为什么两个hash的数据存放顺序是一致的？我说的对吗？谁给解释下？
    
14. my @counter1 = hash2sortedarray(\%m);
    
15. my @counter2 = hash2sortedarray(\%n);
    
16. print "@counter1\n";
    
17. print "@counter2\n";
    
18. 
    
19. if ( @counter1 ~~ @counter2 ) {
    
20.     print "Y\n";
    
21. }
    
22. 
    
23. # 转为数组进行智能匹配
    
24. sub hash2array { return %{$_[0]} }
    
25. sub hash2sortedarray { return map { $_ => $_[0]->{$_} } sort keys %{$_[0]} }

复制代码

rubyish

谢谢啊{:3_188:}

mcshell

学习了~~~{:3_190:}