题目：请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

方法一：递归

import java.util.Arrays;
class Solution {
    public boolean isMatch(String s, String p) {
        // invoke params check
        if (s == null || p == null) {
            return false;
        }
        
        // match core method
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();
        return matchCore(s1, p1);
    }

    public boolean matchCore(char[] s, char[] p) {
        if (s.length == 0 && p.length == 0) {
            return true;
        }

        if (s.length != 0 && p.length == 0) {
            return false;
        }

        if (p.length >= 2 && p[1] == '*') {
            // [] matches a '*'
            if (s.length == 0) {
                return matchCore(s, Arrays.copyOfRange(p, 2, p.length));
            } 
            if (s[0] == p[0] || (p[0] == '.' && s.length != 0)) {
                // move on the next state
                return matchCore(Arrays.copyOfRange(s, 1, s.length), Arrays.copyOfRange(p, 2, p.length))
                // stay on the current state
                || matchCore(Arrays.copyOfRange(s, 1, s.length), p)
                // ignore a '*'
                || matchCore(s, Arrays.copyOfRange(p, 2, p.length));
            } else {
                // ignore a '*'
                return matchCore(s, Arrays.copyOfRange(p, 2, p.length));
            }
        }

        if (s.length == 0) {
            return false;
        } 
        if (s[0] == p[0] || (p[0] == '.' && s.length != 0)) {
            return matchCore(Arrays.copyOfRange(s, 1, s.length), Arrays.copyOfRange(p, 1, p.length));
        }

        return false;
    }
}

方法二：动态规划

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }
}

【算法20】-【正则表达式匹配】

方法一：递归

方法二：动态规划

全站热榜