1. NFA无回溯匹配

拿到题目之后,最先想到的就是构建NFA然后逐字符匹配。可以发现,整个题目的关键之处在于*的处理。首先画出*的状态图,如下:

pre_end状态遇到了*,生成了如上图所示的状态转换,*的处理在tail(end)状态结束。算法如下:

  1. 根据pattern生成对应的NFA
  2. 依次输入待匹配的字符,进行状态转换。转换时同步匹配多个分支,不使用回溯。也就是每次输入结束后可以有多个状态满足要求,参见Regular Expression Matching Can Be Simple And Fast
  3. 输入完所有字符后,检查当前停留的节点中是否有终止节点,有则匹配成功,反之不然。

1.1 NFA的构建

NFA可以由节点与箭头表示,每个节点需要记录以其为起点的箭头,箭头表示由某个字符引发的状态转换,指向目的节点:

static class Node {
    static final char EMPTY_ARROW = 0;  // ε

    int index; // for remain steps estimation
    Map<Character, Node> outArrows = new HashMap<>();

    Node(int index) {
        this.index = index;
    }

    void addArrow(char chr, Node dest) {
        outArrows.put(chr, dest);
    }
}

只需要根据输入的pattern依次构建节点即可,需要记录开始节点用来开始匹配,记录终止节点用来检测是否匹配成功:

Node buildNFA(String pattern) {
    Node start = new Node(0);
    end = start;

    for (int i = 0; i < pattern.length(); i++) {
        char chr = pattern.charAt(i);

        if (chr == '*') {
            // reduce continuous '*' to single one
            if (i - 1 >= 0 && pattern.charAt(i - 1) == '*') continue;

            // do not increase wildcard index
            Node body = new Node(end.index);
            Node tail = new Node(end.index);

            end.addArrow('?', body);
            end.addArrow(Node.EMPTY_ARROW, tail);
            body.addArrow('?', body);
            body.addArrow(Node.EMPTY_ARROW, tail);

            end = tail;

        } else {
            Node node = new Node(end.index + 1);
            end.addArrow(chr, node);
            end = node;
        }
    }
    return start;
}

构建时,可以将连续的*缩减为一个,因为********是等效的。观察上述代码可以注意到,每个Node都有一个与之关联的index值,这关系到匹配时的优化问题,暂且不表,下面会详述。

1.2 NFA的无回溯匹配

由于受到Regular Expression Matching Can Be Simple And Fast 一文的影响,选择了无回溯的匹配方式,将NFA中的各个分支同时进行匹配。比如在pre_end节点遇到*后,当前激活的节点便是pre_endtail,待下一个节点输入后,同时从这两个节点进行状态转换。而不是先随机选一条路径,若无法达到终止节点,再回过来走另一条路径。

我们需要使用Set存储当前激活的节点,因为当pattern中由多个*时,由于body节点的存在自转换(待在原地),会导致通过不同的节点进行状态转换后,到达相同的节点。

转换算法如下:

Node end;
Set<Node> currentNodes = new HashSet<>();

public boolean isMatch(String str, String pattern) {
    Node start = buildNFA(pattern);
    addClosure(end.index, start);

    for (int i = 0; i < str.length(); i++) {
        char chr = str.charAt(i);
        int remainSteps = str.length() - 1 - i;

        Node[] currentCopy = currentNodes.toArray(new Node[currentNodes.size()]);
        currentNodes.clear();

        // step from current nodes
        for (Node node : currentCopy) {
            Node explicit = node.outArrows.get(chr);
            Node wildcard = node.outArrows.get('?');

            if (explicit != null) addClosure(remainSteps, explicit);
            if (wildcard != null) addClosure(remainSteps, wildcard);
        }
    }

    for (Node node : currentNodes) {
        if (node == end) return true;
    }

    return false;
}

算法开始时,先求开始节点的闭包,然后将其中的节点设置为激活状态。接着依次输入字符,进行状态转换。整个NFA只对两种字符进行转换,其一为字母,其二为通配符。转换后,同样要求出转换后状态的闭包。匹配整个字符串的过程中,会不断地更新其激活的当前节点。最后,等到所有输入字符串处理完毕,检查“当前节点”中是否存在终止节点,也就是是否存在合法路径,若有,则匹配成功。

1.3 匹配优化

可以在上面的匹配算法中发现如下代码int remainSteps = str.length() - 1 - i;,这是为优化做准备。由于匹配过程中存在多个正在尝试的路径,当遇到下面的测试用例时,最后会导致几乎所有节点都是激活状态。第一个*会源源不断地向前产生激活的a节点,这些节点会占用绝大多数的匹配时间,但是在匹配结束前不可能到达终点。

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
"*aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa*"

因此,在Node中记录其index,每次匹配字符时,计算剩下未输入的字符最多会使状态前进多少步,若该步数无法到达终点,也就不需要将相应的节点激活了。通过节点的index与终止节点的index进行比较,可以预估步数。在求闭包时剔除无用的节点

void addClosure(int remainSteps, Node node) {
        Node emptyMove = node.outArrows.get(Node.EMPTY_ARROW);

        if (end.index - node.index <= remainSteps){
            currentNodes.add(node);

            if (emptyMove != null) currentNodes.add(emptyMove);
        }
    }

在生成*对应节点时,bodytail使用相同的index

源码见044_Wildcard_Matching.java

2. 基于回溯的NFA

实践之后才发现,在本题的情况下,由于产生分支的情况过于简单,其实匹配时采用回溯的方式可以达到更高的效率。遇到*时,处理方式无非就是两种:其一,走空转换,*不匹配任何字符;其二,*匹配若干字符后走空转换。因此,对于*的处理,可以得到如下算法:

1.遇到*时,默认走空转换,此时,记录待匹配字符在str中的位置为index,进入“尝试阶段”,若尝试失败,会需要回到该位置。 2.继续读取字符,进行状态转换,若发现输入的字符不匹配任何转换,则说明之前对*的处理不正确,尝试失败。于是回到尝试前的状态:待处理字符仍为str[index],此时,在*的状态转换图中,选择由body接收一个字符转换到body,然后进行空转换。也就是尝试用*只匹配一个字符,并更新index。 3.不断地重复步骤2,直到遇到新的*或者字符串末尾,表示对之前的*处理成功。若遇到新的*,则回到步骤1;

以上算法,每次尝试失败后,*的匹配量增加一个字符,不断地进行尝试。为什么遇到新的*就表示之前的*已经成功匹配了呢?前者难道不能匹配更多的字符?因为倘若前者能匹配更多的字符,也可以将其交由后者匹配掉。采用最小原则即可。

既然方法如此简单,可以舍弃生成节点方式,直接在原字符串上面进行状态转移,将字符视为状态即可。用p_ptn表示当前状态,用p_str表示待匹配的字符。p_saved_ptn表示正在尝试匹配的*,而p_saved_str表示开始尝试时最前的未匹配的字符。

public boolean isMatch(String str, String ptn) {
    int p_str = 0; // index of current input str
    int p_ptn = 0; // index of current pattern

    int p_saved_str = -1; // index of latest unmatched str
    int p_saved_ptn = -1; // index of latest unmatched star

    while (p_str < str.length()) {
        char s = str.charAt(p_str);
        char p = p_ptn < ptn.length() ? ptn.charAt(p_ptn) : 0;

        if (s == p || p == '?') {
            p_str++;
            p_ptn++;
        } else if (p == '*') {
            p_saved_ptn = p_ptn++;
            p_saved_str = p_str;
        } else if (p_saved_ptn >= 0) {
            p_ptn = p_saved_ptn + 1;
            p_str = ++p_saved_str;  // '*' matches another char
        } else {
            return false; // characters do not match; p_ptn >= ptn.length() and there is no saved_ptn
        }
    }

    while (p_ptn < ptn.length()) {
        if (ptn.charAt(p_ptn++) != '*') return false;
    }

    return true;
}

源码见044_Wildcard_Matching_2.java

3. 动态规划

dp[i][j]表示patterni位是否能匹配strj位。那么有dp[i][j]=

  1. dp[i-1][j-1], if ptn[i-1]==str[j-1] or ptn[i-1]=='?'
  2. dp[i-1][j] || dp[i-1][j-1] || dp[i-1][j-2] || ... || dp[i-1][0], if ptn[i-1]=='*', 即:
    • dp[i-1][j] || dp[i][j-1]
  3. false, 其它情况

注意ptn[i-1]表示ptn的第i

只需求出i=0以及j=0的情况下dp的值,然后根据上式求出整个dp

public boolean isMatch(String str, String ptn) {
    boolean[][] dp = new boolean[ptn.length() + 1][str.length() + 1];

    dp[0][0] = true;

    for (int i = 1; i <= ptn.length(); i++) {
        dp[i][0] = dp[i - 1][0] && ptn.charAt(i - 1) == '*';
    }

//        for (int j = 1; j <= str.length(); j++) {
//            dp[0][j] = false;
//        }

    for (int i = 1; i <= ptn.length(); i++) {
        for (int j = 1; j <= str.length(); j++) {
            dp[i][j] = ((ptn.charAt(i - 1) == str.charAt(j - 1) || ptn.charAt(i - 1) == '?') && dp[i - 1][j - 1]) ||
                    (ptn.charAt(i - 1) == '*' && (dp[i - 1][j] || dp[i][j - 1]));
        }
    }

    return dp[ptn.length()][str.length()];
}

源码见044_Wildcard_Matching_3.java