Leetcode 10 Regular Expression Matching 简单正则匹配

Implement regular expression matching with support for '.' and '*'.

'.' Matches any single character. '*' Matches zero or more of the
preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be: bool isMatch(const char *s,const
char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a*") → true
isMatch("aa",".*") → true
isMatch("ab",".*") → true
isMatch("aab","c*a*b") → true

难度: Hard

这道题要求我们实现简单的正则表达式的匹配,只要求普通字符 . *的匹配,了解正则的同学都清楚,.代表任意单个字符,*代表0个或多个前面的字符,比如a*可以匹配到空字符串,也可以匹配 a,aaa等等. 题目还要求,我们判定正则是否匹配给定的字符串,要判定整个字符串,而不是其中一部分匹配就算ok.

这是个典型的动态规划的题,作者在leetcode出来之前几乎不做算法,本着死磕到底不看答案不看别人解答的精神,我尝试了不止一种解法,这里贴出两个AC的解法.
任意确定字符,必须精确匹配,. 匹配一个任意字符,这些都很好判定,关键在于,* 到底匹配多少个字符? 这就不好判定了,只能根据一定规则去尝试,这里就是用到动态规划的地方.

第一个AC的解法主要思路为:

1. 切分正则的pattern,将带*号的都切开,比如.aa* 可以切为 .~a~a* 三段

2. 使用一个栈,对不同的可能性(这些可能性实际上形成一个搜索树)做深度优先搜索(也可以不用栈,直接递归,我的代码里没有展示)

3. 对于不带*的分段,直接严格匹配

4. 对于带*的分段,如果跟当前游标处的字符相同,则尝试匹配一个字符(下次判定还可以匹配一个,这样实际可以做到匹配多个),或者匹配0个(也就是将当前子pattern分段抛弃); 如果跟当前游标处的字符不同,则只能匹配0个,将当前子pattern分段抛弃.

代码如下

public class Solution2 {
    public class Symbol {
        public Symbol() {
            rep = false;
        }

        public Symbol(char f,boolean s) {
            c = f;
            rep = s;
        }

        public char    c;
        public boolean rep;
    }

    public class Pair<T> {
        public T first;
        public T second;

        public Pair() {
            first = null;
            second = null;
        }

        public Pair(T _f,T _s) {
            first = _f;
            second = _s;
        }
    }

    /**
     * AC,but slow
     */
    public boolean isMatch(String s,String p) {
        // parse pattern
        List<Symbol> pl = new ArrayList<Symbol>();
        int i = 0;
        while (i < p.length()) {
            char c;
            boolean rep = false;
            char a = p.charAt(i);
            if (a != '*') {
                c = a;
            } else {
                // regex wrong
                return false;
            }
            i++;
            if (i < p.length() && p.charAt(i) == '*') {
                rep = true;
                i++;
            }
            pl.add(new Symbol(c,rep));
        }
        // do match
        Stack<Pair<Integer>> q = new Stack<Pair<Integer>>();
        q.push(new Pair<Integer>(0,0));
        while (!q.isEmpty()) {
            Pair<Integer> pr = q.pop();
            if (isMatch(s,pr.first,pl,pr.second,q)) {
                return true;
            }
        }
        return false;
    }

    private boolean isMatch(String s,int sPos,List<Symbol> pl,int pPos,Stack<Pair<Integer>> q) {
        while (sPos < s.length() && pPos < pl.size()) {
            Symbol sym = pl.get(pPos);
            if (sym.rep) {
                if (sym.c == '.' || sym.c == s.charAt(sPos)) {
                    q.push(new Pair<Integer>(sPos,pPos + 1));
                    q.push(new Pair<Integer>(sPos + 1,pPos));
                } else {
                    q.push(new Pair<Integer>(sPos,pPos + 1));
                }
                return false;
            } else {
                if (sym.c != s.charAt(sPos) && sym.c != '.') {
                    return false;
                }
            }
            sPos++;
            pPos++;
        }
        if (sPos < s.length()) {
            return false;
        }
        if (pPos < pl.size()) {
            while (pPos < pl.size()) {
                if (!pl.get(pPos).rep) {
                    return false;
                }
                pPos++;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Solution2 s = new Solution2();
        System.out.println(s.isMatch("aa","a"));
        System.out.println(s.isMatch("aa","aa"));
        System.out.println(s.isMatch("aaa","aa"));
        System.out.println(s.isMatch("aa","a*"));
        System.out.println(s.isMatch("aa",".*"));
        System.out.println(s.isMatch("aab","c*a*b"));
        System.out.println(s.isMatch("ab",".*"));
        System.out.println(s.isMatch("aaab",".*ab"));
        System.out.println(s.isMatch("aaa","a*a"));
        System.out.println(s.isMatch("aaa","aaab*"));
        System.out.println(s.isMatch("bbab","b*"));
        System.out.println(s.isMatch("bbab","a*"));
        System.out.println(s.isMatch("bbab","b*a*"));
        System.out.println(s.isMatch("bbab","...."));
        System.out.println(s.isMatch("abbabaaaaaaacaa","a*.*b.a.*c*b*a*c*"));
        System.out.println(s.isMatch("bbabaaaaaaacaa","b.a.*c*b*a*c*"));
        System.out.println(s.isMatch("baaaaaaacaa",".*c*b*a*c*"));
        System.out.println(s.isMatch("caa","c*b*a*c*"));
        System.out.println(s.isMatch("caa","c*b*a*"));
        System.out.println(s.isMatch("a","a*b*"));
        System.out.println(s.isMatch("a","a*.*"));
        System.out.println(s.isMatch("ab","a*b"));
        System.out.println(s.isMatch("b",".*b"));
        System.out.println(s.isMatch("ab",".*b"));
        System.out.println(s.isMatch("aaaaaaaaaaaaab","a*a*a*a*a*a*a*a*a*a*a*a*b"));
    }
}

main中包含了测试用例.
这个解法虽然AC了,但是存在以下问题:

1. 执行速度较慢,只超过了百分之几的成功提交.(直接改递归在java中会更快的)

2. 代码思路不是很清晰

3. 这种动态规划比较保守,判定较长,搜索的树比较深.

于是尝试了第二个解法,跟第一个很不同,主要思路为:

1. 首先还是切分正则的pattern,比如.aa* 可以切为 .~a~a* 三段. 不过图方便直接切成多个string即可,其实也有其他的存储方案.

2. 从前/后两个方向,遍历子pattern列表,把不重复(不带*)的部分,跟目标字符串的相应位置做严格匹配,直到遇到带*的子pattern. 此时匹配不成功可以认为正则匹配失败.

3. 剩下的子pattern列表中,如果包含不带*号的子pattern,则寻找所有在目标字符串中能匹配到的字符,对每个这样的字符,把字符串和子pattern列表切分成两段,看这两段是否可以匹配,当且仅当这两段都匹配成功,才算整个字符串匹配正则成功.

4. 剩下的子pattern列表中,如果不包含不带*号的子pattern,即全部都是带*的模糊匹配. 我们就采用贪心算法,对每个子pattern,匹配尽量多的字符,如果能把当前字符串匹配干净,就算ok.

public class Solution3 {
    /**
     * AC,fast enough
     */
    public boolean isMatch(String s,String p) {
        List<String> plist = new ArrayList<String>();
        int pi = 0;
        while (pi < p.length()) {
            if (p.charAt(pi) == '*') {
                // regex wrong
                return false;
            }
            if (pi + 1 < p.length() && p.charAt(pi + 1) == '*') {
                plist.add(p.substring(pi,pi + 2));
                pi += 2;
            } else {
                plist.add(p.substring(pi,pi + 1));
                pi += 1;
            }
        }
        return isMatch(s,s.length(),plist,plist.size());
    }

    /**
     *
     * @param s string to be matched
     * @param ss start position of s (inclusive)
     * @param se end position of s (exclusive)
     * @param plist pattern list
     * @param ps start position of plist (inclusive)
     * @param pe end position of plist (exclusive)
     * @return
     */
    public boolean isMatch(String s,int ss,int se,List<String> plist,int ps,int pe) {
        if (ps == pe) {
            if (ss != se) {
                return false;
            } else {
                return true;
            }
        }
        while (ps < pe && plist.get(ps).length() == 1 && ss < se) {
            char c = plist.get(ps).charAt(0);
            if (c != '.' && c != s.charAt(ss)) {
                return false;
            }
            ss++;
            ps++;
        }
        while (ps < pe && plist.get(pe - 1).length() == 1 && ss < se) {
            char c = plist.get(pe - 1).charAt(0);
            if (c != '.' && c != s.charAt(se - 1)) {
                return false;
            }
            se--;
            pe--;
        }
        if (ps == pe && ss == se) {
            return true;
        }
        if (ps == pe) {
            return false;
        }
        if (ss == se) {
            for (int i = ps; i < pe; i++) {
                if (plist.get(i).length() == 1) {
                    return false;
                }
            }
            return true;
        }
        // select one single sub-pattern
        int pi = 0;
        for (pi = ps; pi < pe; pi++) {
            if (plist.get(pi).length() == 1) {
                break;
            }
        }
        if (pi < pe) {
            // found single sub-pattern
            char c = plist.get(pi).charAt(0);
            for (int si = ss; si < se; si++) {
                if (c == '.' || s.charAt(si) == c) {
                    boolean b1 = isMatch(s,ss,si,ps,pi);
                    if (!b1) {
                        // early termination
                        continue;
                    }
                    boolean b2 = isMatch(s,si + 1,se,pi + 1,pe);
                    if (b2) {
                        return true;
                    }
                }
            }
            return false;
        }
        // single sub-pattern not found,all * patterns
        // do greedy
        for (pi = ps; pi < pe; pi++) {
            char c = plist.get(pi).charAt(0);
            if (c == '.') {
                // will consume all
                return true;
            }
            while (ss < se && (s.charAt(ss) == c)) {
                ss++;
            }
            if (ss == se) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution3 s = new Solution3();
        System.out.println(s.isMatch("aa","a*a*a*a*a*a*a*a*a*a*a*a*b"));
    }
}

main中包含了测试用例.
这个解法看代码直觉就可以感到搜索深度会相对于上个解法小很多,因为能在本次判定中完成的,就在本次判定中完成,不放到下次. 实际也可以超过75%的提交,并且思路相对清晰的多,虽然代码长了点.
可以看到,对于动态规划的问题,需要做的是:

• 确定的部分尽快匹配,给出答案

• 不确定的部分,单独切分出来,使用动态规划

以上是我的解法,不知道是否有更好更清晰的解.

另: 这道题跟 Leetcode 44 通配符匹配很相似,稍后给出Leetcode 44的解.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!