Solution by awice


  • 0

    Approach #1: Recursion [Accepted]

    Intuition

    If there were no Kleene stars (the * wildcard character for regular expressions), the problem would be easier - we simply check from left to right if each character of the text matches the pattern.

    When a star is present, we may need to check many different suffixes of the text and see if they match the rest of the pattern. A recursive solution is a straightforward way to represent this relationship.

    Algorithm

    Without a Kleene star, our solution would look like this:

    def match(text, pattern):
        if not pattern: return not text
        first_match = bool(text) and pattern[0] in {text[0], '.'}
        return first_match and match(text[1:], pattern[1:])
    

    If a star is present in the pattern, it will be in the second position pattern[1]. Then, we may ignore this part of the pattern, or delete a matching character in the text. If we have a match on the remaining strings after any of these operations, then the initial inputs matched.

    Python

    class Solution(object):
        def isMatch(self, text, pattern):
            if not pattern:
                return not text
    
            first_match = bool(text) and pattern[0] in {text[0], '.'}
    
            if len(pattern) >= 2 and pattern[1] == '*':
                return (self.isMatch(text, pattern[2:]) or
                        first_match and self.isMatch(text[1:], pattern))
            else:
                return first_match and self.isMatch(text[1:], pattern[1:])
    

    Java

    class Solution {
        public boolean isMatch(String text, String pattern) {
            if (pattern.isEmpty()) return text.isEmpty();
            boolean first_match = (!text.isEmpty() && 
                                   (pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
            
            if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
                return (isMatch(text, pattern.substring(2)) || 
                        (first_match && isMatch(text.substring(1), pattern)));
            } else {
                return first_match && isMatch(text.substring(1), pattern.substring(1));
            }
        }
    }
    

    Complexity Analysis

    • Time Complexity: Let $$T, P$$ be the lengths of the text, pattern respectively. In the worst case, a call to match(text[i:], pattern[2j:]) will be made $$\binom{i+j}{i}$$ times, and strings of order $$O(T - i)$$ and $$O(P - 2j)$$ will be made. Thus, the complexity has order $$\sum_{i = 0}^T \sum{j = 0}^{P/2} \binom{i+j}{i} O(T+P-i-2j)$$. With some effort outside the scope of this article, we can show this is bounded by $$O((T+P)2^{T + P/2})$$.

    • Space Complexity: For every call to match, we will create those strings as described above, possibly creating duplicates. If memory is not freed, this will also take a total of $$O((T+P)2^{T + P/2})$$ space, even though there are only order $$O(T^2 + P^2)$$ unique suffixes of $$P, T$$ that are actually required.


    Approach #2: Dynamic Programming [Accepted]

    Intuition

    As the problem has an optimal substructure, it is natural to cache intermediate results. We ask the question dp(i, j): does text[i:] and pattern[j:] match? We can describe our answer in terms of answers to questions involving smaller strings.

    Algorithm

    We proceed with the same recursion as in Approach #1, except because calls will only ever be made to match(text[i:], pattern[j:]), we use dp(i, j) to handle those calls instead, saving us expensive string-building operations and allowing us to cache intermediate results.

    Python

    Top-Down Variation

    class Solution(object):
        def isMatch(self, text, pattern):
            memo = {}
            def dp(i, j):
                if (i, j) not in memo:
                    if j == len(pattern):
                        ans = i == len(text)
                    else:
                        first_match = i < len(text) and pattern[j] in {text[i], '.'}
                        if j+1 < len(pattern) and pattern[j+1] == '*':
                            ans = dp(i, j+2) or first_match and dp(i+1, j)
                        else:
                            ans = first_match and dp(i+1, j+1)
    
                    memo[i, j] = ans
                return memo[i, j]
    
            return dp(0, 0)
    

    Bottom-Up Variation

    class Solution(object):
        def isMatch(self, text, pattern):
            dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]
    
            dp[-1][-1] = True
            for i in range(len(text), -1, -1):
                for j in range(len(pattern) - 1, -1, -1):
                    first_match = i < len(text) and pattern[j] in {text[i], '.'}
                    if j+1 < len(pattern) and pattern[j+1] == '*':
                        dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
                    else:
                        dp[i][j] = first_match and dp[i+1][j+1]
    
            return dp[0][0]
    

    Java

    Top-Down Variation

    enum Result {
        TRUE, FALSE
    }
    
    class Solution {
        Result[][] memo;
            
        public boolean isMatch(String text, String pattern) {
            memo = new Result[text.length() + 1][pattern.length() + 1];
            return dp(0, 0, text, pattern);
        }
        
        public boolean dp(int i, int j, String text, String pattern) {
            if (memo[i][j] != null) {
                return memo[i][j] == Result.TRUE;
            }
            boolean ans;
            if (j == pattern.length()){
                ans = i == text.length();
            } else{
                boolean first_match = (i < text.length() && 
                                       (pattern.charAt(j) == text.charAt(i) ||
                                        pattern.charAt(j) == '.'));
    
                if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                    ans = (dp(i, j+2, text, pattern) || 
                           first_match && dp(i+1, j, text, pattern));
                } else {
                    ans = first_match && dp(i+1, j+1, text, pattern);
                }
            }
            memo[i][j] = ans ? Result.TRUE : Result.FALSE;
            return ans;
        }
    }
    

    Bottom-Up Variation

    class Solution {
        public boolean isMatch(String text, String pattern) {
            boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
            dp[text.length()][pattern.length()] = true;
            
            for (int i = text.length(); i >= 0; i--){
                for (int j = pattern.length() - 1; j >= 0; j--){
                    boolean first_match = (i < text.length() && 
                                           (pattern.charAt(j) == text.charAt(i) ||
                                            pattern.charAt(j) == '.'));
                    if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
                        dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
                    } else {
                        dp[i][j] = first_match && dp[i+1][j+1];
                    }
                }
            }
            return dp[0][0];
        }
    }
    

    Complexity Analysis

    • Time Complexity: Let $$T, P$$ be the lengths of the text, pattern respectively. The work for every call to dp(i, j) $$(i=0 ... T; j=0 ... P)$$ is done once, and it is $$O(1)$$ work. Hence, the time complexity is $$O(TP)$$.

    • Space Complexity: The only memory we use is the $$O(TP)$$ boolean entries in our cache. Hence, the space complexity is $$O(TP)$$.


Log in to reply
 

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