10. Regular Expression Matching

Description

Given an input string (s) and a pattern (p), 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).

Note:

• s could be empty and contains only lowercase letters a-z.

• p could be empty and contains only lowercase letters a-z, and characters like . or *.

Constraints

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input:

s = "aa"

p = "a"

Output: false

Explanation: "a" does not match the entire string "aa".

Example 2

Input:

s = "aa"

p = "a*"

Output: true

Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3

Input:

s = "ab"

p = ".*"

Output: true

Explanation: "." means "zero or more (*) of any character (.)".

Example 4

Input:

s = "aab"

p = "cab"

Output: true

Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5

Input:

s = "mississippi"

p = "mis*is*p*."

Output: false

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null) return false;
        return s.matches(p);
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public boolean isMatch(String s, String p) {
        if(s == null) return false;
        int sLen = s.length(), pLen = p.length();
        boolean[][] dp = new boolean[sLen+1][pLen+1];
        dp[0][0] = true;
        
        for(int i = 0; i <= sLen; i++) {
            for(int j = 1; j <= pLen; j++) {
                if(i == 0) {
                    if(p.charAt(j-1) == '*') {
                        dp[i][j] = dp[i][j-2];
                    }
                    continue;
                }
                char sc = s.charAt(i-1);
                char pc = p.charAt(j-1);
                if(sc == pc || pc == '.') {
                    dp[i][j] = dp[i-1][j-1];
                } else if(pc == '*') {
                    pc = p.charAt(j-2);
                    if(sc == pc || pc == '.') {
                        dp[i][j] = dp[i][j-1] | dp[i-1][j];
                    }
                    dp[i][j] = dp[i][j] | dp[i][j-2];
                }
            }
        }
        return dp[sLen][pLen];
    }
}

Follow up