西西軟件園多重安全檢測下載網(wǎng)站、值得信賴的軟件下載站!
軟件
軟件
文章
搜索

首頁編程開發(fā)其它知識 → 兄弟字符串怎么判斷、如何迅速匹配兄弟字符串?

兄弟字符串怎么判斷、如何迅速匹配兄弟字符串?

相關(guān)軟件相關(guān)文章發(fā)表評論 來源:圣歌時間:2011/12/25 2:40:40字體大小:A-A+

作者:圣歌點擊:178次評論:18次標簽: 字符串

  • 類型:電子教程大。9.5M語言:中文 評分:8.0
  • 標簽:
立即下載

如果兩個字符串的字符一樣,但是順序不一樣,被認為是兄弟字符串,問如何迅速匹配兄弟字符串?

首先:接到題目,匹配字符串,這不簡單了,遍歷嘛。。
方法一:
步驟如下:
  1.判斷兩個字符串的長度是否一樣。
  2.循環(huán)提取第一個字符串的字符去第二個字符串中尋找是否存在?
  3.全部都有則是兄弟字符串,其他則不是兄弟字符串。

時間復雜度N*N/2 ,平方級。
額,這算法真的就正確么??????
來看看這種情況:字符串A為aab;字符串B為abc,一看就知道它們是false,那按照上面我寫的算法得出的結(jié)論卻是true。
上面的算法錯誤的,考慮不周,那以遍歷這種思路到底是否能判斷兄弟字符串?
能,只要把上面的算法第2步稍微改動一下,改為“2.循環(huán)提取第一個字符串的字符去第二個字符串中尋找是否存在?存在則移除第二個字符串中的那個字符!
好了,遍歷思路算是可以解決了這個問題了。
不過嘛,遍歷思路的時間復雜度是指數(shù)級,太耗時間,性能不好。

方法二:
賦予字符額外的意義。什么意思了,給26個字符依次賦予質(zhì)數(shù)。質(zhì)數(shù)是比較特殊的一堆數(shù)字,它們只能被1和本身整除。
給a賦值2、給b賦值3、給c賦值5、給d賦值7、給e賦值11、給f賦值13 等等……
好了,給兩個字符串中的所有字符都賦值了,,接著讓它們各自相加,如果兩個字符串得出的結(jié)果是一樣的,那它們是兄弟字符串。。
嘎嘎,時間復雜度是常數(shù)。性能好了是不????
別太高興了,這個算法到目前為止也是有問題的,來看看這種情況:bf和ce不是兄弟字符串,按照上面的賦值規(guī)律b+f=3+13=16;c+e=5+11=16 ,看吧,明明他們就不是兄弟字符串,但是按照上面的算法就錯了。
怎么解決這個問題了?用乘積:每個字符串內(nèi)部求乘積,相等就是兄弟字符串。
好了,這算法是正確的,但是呢,又有個算法外的問題:字符串相乘及其容易出現(xiàn)結(jié)果溢出,說得簡單點就是乘積太大了,大于程序語言的內(nèi)置的整數(shù)類型(int、long)所能表示的最大值。這怎么解決?有個比較偏的方法就是用數(shù)組來存儲乘積。具體方法我不說了,跟本偏文章無關(guān)。。。
那怎么解決兄弟字符串的問題???用平方和或者立方和。。。。。既然直接用加法不行,用乘法還會溢出。那換個思路用平方和。。。
b*b+f*f=3*3+13*13=178;c*c+e*e=5*5+11*11=146
看吧它們不是兄弟字符串吧。。。。。


這只是我的算法思路,可能有誤,僅供參考。。。。

@萬倉一黍
你說的思路能行,但是這兩個數(shù)組該如何實現(xiàn)????
首先,數(shù)組是種鍵值對,而常用的編程語言(C、C++、C#、java)中數(shù)組的鍵都是數(shù)字,你說得用數(shù)組記錄字符串中的各個字符出現(xiàn)的次數(shù)該如何操作??????
ascii編碼表不是有編碼0到255總共256個字符,聲明2個長度為256的一維數(shù)組,把兩個字符串中的字符轉(zhuǎn)換為ascii表中的編碼后,之后在對應(yīng)的數(shù)組單元中加1,最后對比兩個數(shù)組。

額,另外,用哈希表是否可以實現(xiàn)?對哈希表不太了解,不好判斷。。。
用數(shù)組實現(xiàn),很簡單的。定義兩個數(shù)組a(255),b(255)
遍歷兩個字符串,遇到字符的時候,直接利用該字符的Ascii碼來獲得在數(shù)組中的位置。如a(asc(char))++

    相關(guān)評論

    閱讀本文后您有什么感想? 已有人給出評價!

    • 8 喜歡喜歡
    • 3 頂
    • 1 難過難過
    • 5 囧
    • 3 圍觀圍觀
    • 2 無聊無聊

    熱門評論

    最新評論

    發(fā)表評論 查看所有評論(18)

    昵稱:
    表情: 高興 可 汗 我不要 害羞 好 下下下 送花 屎 親親
    字數(shù): 0/500 (您的評論需要經(jīng)過審核才能顯示)