一个字符串匹配的题目

sammyjeep

回复 19# kk861123


    对于楼主的例子的确是可以的，不过如果字符串再长一些，比如500个，这个性能可能就不能接受了，虽然方法变了，本质（遍历字符串）没变。
   这个问题还要看具体的场景。

kk861123

回复 21# sammyjeep


    您说的很有道理，要看环境

afukada

不知道思路上有沒有錯

還請大家指教一下

踩在前面一些方法之下

想法：

遍歷其中一個字串

另一個字串用最少的計算次數

先驗證str1字串長度等於str2字串長度

然後對每一個str1的字元做hash(%count)

然後用的s///g對於每個hash(%count)的$key來作取代並計算取代的次數

計算取代的次數是不是等於$count{$key}的value

如果hash(%count)的value等於1的時候

表示str1已經等於str2(因為剩下的字元的出現一次)

則表示str1 eq str2

如果在作取代的過程中發現有取代的次數不等於$count{$key}的value

則表示str1 ne str2

code如下：

1. $str1="abcda";
   
2. $str2="adabc";
   
3. $check=0;
   
4. 
   
5. if(length($str1)==length($str2))
   
6. {
   
7.         my @str1_s=split(//,$str1);
   
8.        
   
9.         for(@str1_s)
   
10.         {
    
11.                 $count{$_}++;
    
12.                 $check++ if($count{$_}>=2);
    
13.         }
    
14.        
    
15.         if($check==0)
    
16.         {
    
17.                 print $str1,"=",$str2,"\n";
    
18.         }
    
19.         else
    
20.         {
    
21.                 $check=0;
    
22.                
    
23.                 foreach(sort{$count{$a}<=>$count{$b}}keys($count))
    
24.                 {
    
25.                         if($count{$_}>1)
    
26.                         {
    
27.                                 print $str1,"!=",$str2,"\n" if($count{$_}!=($str2=~s/$_//g));
    
28.                         }
    
29.                         else
    
30.                         {
    
31.                                 print $str1,"=",$str2,"\n" if($check==0);
    
32.                                 last;
    
33.                         }
    
34.                 }
    
35.         }
    
36. }
    
37. 
    
38. print $str1,"==",$str2,"\n" if($check==0);

复制代码

如果code有問題請告訴我

這個方法我目前想到的問題

1.字串太短等於做了很多多餘的事

2.應該要設一個字串長度以上在做這個驗證

3.排序我是依據所需要的element來做設計，我的想法是越少的element越快

不知道大家有什麼意見

還請大家指教

獻醜了<(_._)>

sammyjeep

回复 22# kk861123


    主要还是看算法的时间复杂度，遍历字符串本身就是O(n)，理论上split //, xxx 也应该是O(n)，当然由于 split本身是perl内部已经实现了，可能比代码中的遍历更快一点。如果人用一个算法时间复杂度小于O(n)，应该可以提高不少速度吧，抛砖引玉，呵呵。