Code Jam字符串匹配

我們給出了兩個Pattern.A模式只包含大寫/小寫英文字母和星號（*）。
星號可以匹配zero and four之間的字母。

例如，GoneGirl和GoneTomorrow匹配模式Gone **，但帶有標題TheGoneGirl和GoneWithTheWind的書不能。
Question Link Code Jam字符串匹配

我們必須找出是否有字符串匹配匹配兩種模式。

我的方法：動態編程維護一個二維數組。

M[0][0]=true; 

for(int i=1;i<=S.length();i++){ 

for(int j=1;j<=A.length();j++){ 

     if(!M[i-1][j-1]) continue; 

     if(S.charAt(i-1)=='*'){ 

      for(int k=0;k<4;k++) M[i][j+k]=true; 

      M[i][j-1]=true; 
     } 

     if(A.charAt(j-1)=='*'){ 

      for(int k=0;k<4;k++) M[i+k][j]=true; 

      M[i-1][j]=true; 
     } 

     if(S.charAt(i-1)==A.charAt(j-1)) M[i][j]=true; 


}

有人可以幫我在我的算法中出了什麼問題嗎？

來源

2017-03-05 Narendra Modi

第一步應該是找到失敗的測試用例。 –

相關：https://stackoverflow.com/questions/34009784/checking-collision-in-filename-search-patterns-with-wildcards/ – m69

您的代碼看起來幾乎正確。但是，考慮這個例子 -

A = "*" 
B = "****"

在這裏，你讓dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = true但對於B每個*，可以有另外4個* S，共16分。在這種情況下，你的程序將不起作用。

一個安全的方法是在進行DP計算之前用4 *替換每個*以預處理字符串。然後對於每個*，您可以匹配一個字母或跳過。我被這種方法所接受。

來源

2017-03-05 10:05:16

Code Jam字符串匹配

回答

相關問題