兩個字符串之間的精確匹配 - 線性編輯距離？

這是一個問題，因爲字符串的字符來自：a-z，.,*，另一個字符串的字符來自a-z。其中*可以刪除之前的字符，否則會被跳過並且.可以匹配任何單個字符。問題是第一個字符串是否可以匹配第二個字符串。兩個字符串之間的精確匹配 - 線性編輯距離？

注：這是問題，因爲我找到了聲明，但在這種情況下，字符*執行相同的功能，在正則表達式?。

例子：

isMatch("a*", "") = true; //"a*" could be "a" or an empty string "" 
isMatch(".", "") = false; 
isMatch("ab*", "a") = true; 
isMatch("a.", "ab") = true; 
isMatch("a", "a") = true;

我用稍微修改的編輯距離，我只知道一個二維動態規劃方法已經解決了這個問題。我想知道是否存在這個問題的線性解決方案，也許它沒有dp方法是可以解決的？

來源

2013-10-14 Kevin Bello

*匹配多個副本嗎？例如，什麼是'isMatch（「aaaaaa」，「a *」）'？ – templatetypedef

否，*只能刪除之前的字符。第二個字符串只包含來自az的字符，所以它應該是isMatch（「a *」，「aaaaaa」），答案是錯誤的，因爲正如我在上面的例子中所說的「a *」可能是「a」 case *省略）或「」（*刪除字符a）。我忘記提及*僅出現在a-z或'。'中的字符之後，所以不可能有這樣的「a **」或「* a *」'。 –

好吧...所以*類似於？運算符在正則表達式中？ – templatetypedef

感謝@RealzSlaw的建議。我的問題是尋找一個線性解決方案，這似乎是不可能的，只是因爲這種情況下的（現在正則表達式語法）：

isMatch("a?a?b?b?b?a?a?b?a?","abbab")

它要求abbab是否是aabbbaaba子序列，這是一個NP難作爲據我所知，所以線性解決方案似乎是不可行的。

來源

2013-10-22 19:28:54

兩個字符串之間的精確匹配 - 線性編輯距離？

回答

相關問題