My concise recursive and DP solutions with full explanation in C++


  • 230
    X

    Please refer to my blog post if you have any comment. Wildcard matching problem can be solved similarly.

    class Solution {
    public:
        bool isMatch(string s, string p) {
            if (p.empty())    return s.empty();
            
            if ('*' == p[1])
                // x* matches empty string or at least one character: x* -> xx*
                // *s is to ensure s is non-empty
                return (isMatch(s, p.substr(2)) || !s.empty() && (s[0] == p[0] || '.' == p[0]) && isMatch(s.substr(1), p));
            else
                return !s.empty() && (s[0] == p[0] || '.' == p[0]) && isMatch(s.substr(1), p.substr(1));
        }
    };
    
    class Solution {
    public:
        bool isMatch(string s, string p) {
            /**
             * f[i][j]: if s[0..i-1] matches p[0..j-1]
             * if p[j - 1] != '*'
             *      f[i][j] = f[i - 1][j - 1] && s[i - 1] == p[j - 1]
             * if p[j - 1] == '*', denote p[j - 2] with x
             *      f[i][j] is true iff any of the following is true
             *      1) "x*" repeats 0 time and matches empty: f[i][j - 2]
             *      2) "x*" repeats >= 1 times and matches "x*x": s[i - 1] == x && f[i - 1][j]
             * '.' matches any single character
             */
            int m = s.size(), n = p.size();
            vector<vector<bool>> f(m + 1, vector<bool>(n + 1, false));
            
            f[0][0] = true;
            for (int i = 1; i <= m; i++)
                f[i][0] = false;
            // p[0.., j - 3, j - 2, j - 1] matches empty iff p[j - 1] is '*' and p[0..j - 3] matches empty
            for (int j = 1; j <= n; j++)
                f[0][j] = j > 1 && '*' == p[j - 1] && f[0][j - 2];
            
            for (int i = 1; i <= m; i++)
                for (int 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
                        // p[0] cannot be '*' so no need to check "j > 1" here
                        f[i][j] = f[i][j - 2] || (s[i - 1] == p[j - 2] || '.' == p[j - 2]) && f[i - 1][j];
            
            return f[m][n];
        }
    };
    

  • 1
    O

    your dynamic programming solution is perfect.


  • 1
    L

    this is the best answer i have seen under this problem!


  • 0
    E
    This post is deleted!

  • 0
    X

    I had difficulty understanding other answers, so I came up with an easy-to-understand one.


  • 0
    T

    DP may be the proper way. My recursive solution in python always goes overtime.


  • 0
    X

    Seconded. Recursion is mainly for showing the basic idea.


  • 0
    X

    Great solution! Just one comment: I feel " 2) "x*" repeats 1 time and matches x: b[i + 1][j]" is not necessary since condition (3) includes it already:


  • 0
    X

    @xinxiang You are right, nice catch. It is inconsistent with the recursive version. I updated both versions. Please let me know if there is any other issue.


  • 7
    H

    How could you ensure the 'p[1]' and 'p.substr(2)' is exist ,but not overflow?


  • 2
    X

    (A) p[1]: If pos is equal to the string length, the function returns a reference to the null character http://www.cplusplus.com/reference/string/string/operator[]/. (B)
    p.substr(2): only called when p[1] is '*', so p's length is at least 2 and substr(2) is good http://www.cplusplus.com/reference/string/string/substr/.


  • 0
    H

    Thank you.your answer is the best i had even see util now.


  • 0
    M
    This post is deleted!

  • 22
    M

    Java equivalent

    public boolean isMatch(String s, String p) {
        /*
            'match' below including .
        f(i,j) means s where s.len=i matches p where p.len=j
        f(i,j) =
            if (p_j-1 != * ) f(i-1, j-1) and s_i-1 matches p_j-1
            if (p_j-1 == * )
                * matches zero times: f(i,j-2)
                or * matches at least one time: f(i-1,j) and s_i-1 matches p_j-2
         */
    
        if (!p.isEmpty() && p.charAt(0) == '*') {
            return false;   // invalid p
        }
    
        boolean[][] f = new boolean[s.length() + 1][p.length() + 1];
    
        // initialize f(0,0)
        f[0][0] = true;
    
        // f(k,0) and f(0,2k-1) where k>=1 are false by default
    
        // initialize f(0,2k) where p_2k-1 = * for any k>=1
        for (int j = 1; j < p.length(); j+=2) {
            if (p.charAt(j) == '*') {
                f[0][j+1] = f[0][j-1];
            }
        }
    
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= p.length(); j++) {
                if (p.charAt(j - 1) != '*') {
                    f[i][j] = f[i - 1][j - 1] && isCharMatch(s.charAt(i - 1), p.charAt(j - 1));
                } else {
                    f[i][j] = f[i][j - 2] || f[i - 1][j] && isCharMatch(s.charAt(i - 1), p.charAt(j - 2));
                }
            }
        }
    
        return f[s.length()][p.length()];
    }
    
    // no * in p
    private boolean isCharMatch(char s, char p) {
        return p == '.' || s == p;
    }

  • 2
    R

    What is the run time of your recursive solution ? If you please mention.


  • 0
    D

    Nice code!
    Can you explain why we must initialize f(0,2k) where p_2k-1 = * ? I know it is necessary but I don't understand why.


  • 0
    M

    f(i, j) depends on f(i-1, j) or f(i, j-1) which means that i will hit zero while j is still greater than 0. In this case f(0, someJ) cannot be evaluated recursively because i cannot be reduced further more i.e. f(-1, someJ) is not valid


  • 0
    K

    Hi, how do you know p[0] cannot be * ?


  • 2
    B

    if p[0] = '*', the string must be an invalid string.
    that is what Regular Expression defined.


  • 0
    N
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.