10. Regular Expression Matching.md

10. Regular Expression Matching

Problem

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

tag:

• dp

Solution

/f(i, j): s前i个字符与p前j个字符匹配
//if p[j-1]!=*  
//   f(i, j) = f(i-1, j-1) && s[i-1]==p[j-1] || p[j-1]==. 
//else
//   f(i,j) = f(i, j-2) || ( f(i-1,j) && ...)
//ref: https://leetcode.com/discuss/18970/concise-recursive-and-dp-solutions-with-full-explanation-in

java

    public boolean isMatch(String s, String p) {
        if(s==null || p==null) return false;
        
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m+1][n+1];
        f[0][0] = true;
        for(int j=1; j<=n; j++) f[0][j] = j>1 && f[0][j-2] && p.charAt(j-1)=='*';
        
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(p.charAt(j-1)!='*') {
                    f[i][j] = f[i-1][j-1] && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.');
                } else {
                    f[i][j] = j>1 && (f[i][j-2] || (f[i-1][j] && (s.charAt(i-1)==p.charAt(j-2)||p.charAt(j-2)=='.')));
                }
            }
        }
        return f[m][n];
    }

go

func isMatch(s, p string) bool {
	m, n := len(s), len(p)
	f := make([][]bool, m+1)
	for i := 0; i <= m; i++ {
		f[i] = make([]bool, n+1)
	}
	f[0][0] = true
	for j := 1; j <= n; j++ {
		f[0][j] = j > 1 && f[0][j-2] && p[j-1] == '*'
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if p[j-1] != '*' {
				f[i][j] = f[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.')
			} else {
				f[i][j] = j > 1 && (f[i][j-2] || (f[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.')))
			}
		}
	}
	return f[m][n]
}