检查两种模式是否相互匹配？

解决这个更普遍的问题的原因是它使我们能够使用围绕正则表达式开发的理论.例如,在形式语言理论中,我们可以谈论正则表达式的语言,正则表达式是正则表达式匹配的所有字符串的集合.我们可以表示这个L(R).如果有一个字符串与两个正则表达式R1和R2匹配,那么该字符串属于L(R1)和L(R2),所以我们的问题相当于

给定两个正则表达式R1和R2,L(R1)∩L(R2)中是否有一个字符串w？

到目前为止,我们所做的只是重新构建我们想要解决的问题.现在让我们来解决它.

这里的关键步骤是可以将任何正则表达式转换为NFA(非确定性有限自动机),以便正则表达式匹配的每个字符串都被NFA接受,反之亦然.更好的是,得到的NFA可以在多项式时间内构造.因此,让我们首先为每个输入正则表达式构建NFA.

现在我们有了这些NFA,我们想回答这个问题:两个NFA都接受一个字符串吗？幸运的是,有一种快速回答这个问题的方法.在NFA上有一个共同的结构,称为产品结构,给定两个NFA和N2,构造一个新的NFA N',接受N1和N2接受的所有字符串,而不接受其他字符串.同样,这种结构在多项式时间内运行.

一旦我们拥有N',我们基本上就完成了!我们所要做的就是在N'状态下进行广度优先或深度优先搜索,看看我们是否找到了接受状态.如果是这样,太好了!这意味着N'接受了一个字符串,这意味着N1和N2都接受了一个字符串,这意味着R1和R2都匹配了一个字符串,因此原始问题的答案是"是的!" 相反,如果我们无法达到接受状态,那么答案就是"不,这是不可能的".

我确信有一种方法可以通过在自动机N'上进行某种隐式BFS而不实际构造它来隐式地完成所有这些操作,并且应该可以在类似时间O(n ²)的情况下执行此操作.如果我有更多时间,我会重温这个答案并扩展如何做到这一点.

Answer 2

Cod*_*ter 2

我对 DP 的想法进行了研究，并提出了上述问题的以下实现。如果有人发现任何测试用例失败，请随时编辑代码。从我这边来看，我尝试了一些测试用例并通过了所有测试用例，我也将在下面提到。

请注意，我扩展了用于regex使用 DP 解决与字符串的模式匹配的想法。要参考这个想法，请参阅 OP 中提供的 LeetCode 链接并留意讨论部分。regex他们给出了匹配和字符串的解释。

这个想法是创建一个动态记忆表，其条目将遵循以下规则：

如果模式 1[i] == 模式 2[j]，则 dp[i][j] = dp[i-1][j-1]
如果模式1[i] == '.' 或pattern2[j] == '.'，则 dp[i][j] = dp[i-1][j-1]
诀窍就在这里：如果pattern1[i] = '*'，那么如果dp[i-2][j]存在，那么dp[i][j] = dp[i-2][j] || dp[i][j-1] 否则 dp[i][j] = dp[i][j-1]。
如果pattern2[j] == '*'，则如果pattern1[i] == pattern2[j-1]，则 dp[i][j] = dp[i][j-2] || dp[i-1][j] 否则 dp[i][j] = dp[i][j-2]

pattern1按行进行，pattern2按列进行。另外，请注意，此代码也适用于与任何给定字符串匹配的正常正则表达式模式。我已经通过在 LeetCode 上运行它来验证它，并且它通过了那里所有可用的测试用例！

下面是上述逻辑的完整工作实现：

boolean matchRegex(String pattern1, String pattern2){
    boolean dp[][] = new boolean[pattern1.length()+1][pattern2.length()+1];
    dp[0][0] = true;
            //fill up for the starting row
    for(int j=1;j<=pattern2.length();j++){
        if(pattern2.charAt(j-1) == '*')
            dp[0][j] = dp[0][j-2];

    }
            //fill up for the starting column
    for(int j=1;j<=pattern1.length();j++){
        if(pattern1.charAt(j-1) == '*')
            dp[j][0] = dp[j-2][0];

    }

            //fill for rest table
    for(int i=1;i<=pattern1.length();i++){
        for(int j=1;j<=pattern2.length();j++){
                        //if second character of pattern1 is *, it will be equal to 
                        //value in top row of current cell
                        if(pattern1.charAt(i-1) == '*'){
                            dp[i][j] = dp[i-2][j] || dp[i][j-1];
                        }

                        else if(pattern1.charAt(i-1)!='*' && pattern2.charAt(j-1)!='*' 
                                    && (pattern1.charAt(i-1) == pattern2.charAt(j-1) 
                                    || pattern1.charAt(i-1)=='.' || pattern2.charAt(j-1)=='.'))
                dp[i][j] = dp[i-1][j-1];
                        else if(pattern2.charAt(j-1) == '*'){
                boolean temp = false;
                if(pattern2.charAt(j-2) == pattern1.charAt(i-1) 
                                            || pattern1.charAt(i-1)=='.' 
                                            || pattern1.charAt(i-1)=='*' 
                                            || pattern2.charAt(j-2)=='.') 

                    temp = dp[i-1][j];
                dp[i][j] = dp[i][j-2] || temp;

            }
        }
    }
            //comment this portion if you don't want to see entire dp table
            for(int i=0;i<=pattern1.length();i++){
                for(int j=0;j<=pattern2.length();j++)
                    System.out.print(dp[i][j]+" ");
                System.out.println("");
            }
    return dp[pattern1.length()][pattern2.length()];
}

Run Code Online (Sandbox Code Playgroud)

驱动方法：

System.out.println(e.matchRegex("bdbaa.*", "bdb.*daa"));

Input1: bdbaa.* and bdb.*daa
Output1: true

Input2: .*acd and .*bce
Output2: false

Input3: acd.* and .*bce
Output3: true

Run Code Online (Sandbox Code Playgroud)

时间复杂度：O(mn)其中m和n是给定的两个正则表达式模式的长度。空间复杂度也是如此。

归档时间：	8 年，7 月前
查看次数：	844 次
最近记录：	8 年，6 月前