algorithm - Code Jam 字符串匹配

Question

我们给出了两种模式。一种模式仅由大写/小写英文字母和星号 (*) 组成。
星号可以匹配零到四个字母。

例如，GoneGirl 和 GoneTomorrow 匹配模式 Gone**，但标题为 TheGoneGirl 的书籍和GoneWithTheWind 不能。
Question Link

我们必须找出匹配的字符串是否匹配两个模式。

我的方法:动态规划维护一个二维数组。

 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;


}

有人能帮我看看我的算法有什么问题吗？

Answer 1

您的代码看起来几乎是正确的。但是，考虑这个例子 -

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

给你 dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = true但对于每个 *在 B , 可以有另一个 4 * s，一共16颗星。在这种情况下，您的程序将无法运行。

一种安全的方法是通过替换每个 * 来预处理字符串与 4 *在进行 DP 计算之前。然后对于每个 * , 您可以匹配一个字母或跳过。我被这种方法接受了。