Regular Expression Matching

Problem Statement

The objective is to determine if a given input string s can be matched against a pattern p. The pattern incorporates two special characters: '.', which can represent any single character, and '*', which can represent zero or more of the character that directly precedes it. The challenge lies in ensuring that the pattern matches the entire string s, not just part of it. This task involves recognizing the sequence and potentially repetitive patterns within the string as dictated by p to ensure a full match.

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 (.)".

Constraints

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Approach and Intuition

The problem can be approached by understanding the roles of the special characters and the string manipulation they imply:

1. Understanding the Special Characters:

   • '.' matches any single character – This broadens the scope of matching any letter at a specific position where '.' appears in the pattern.
   • '*' matches zero or more of the immediately preceding element – This introduces repetition and requires careful attention as it can match an empty sequence or multiple sequences of the previous character.

2. Steps to Approach the Problem:

   • Start Matching from the Beginning: Traverse both the string s and the pattern p from the beginning, checking for direct matches or special character conditions.
   • Handle '*' Character: When encountering a '*', decide whether to skip the preceding element (consider it zero times) or to include multiple instances of it. Adjust the traversal of s and p accordingly.
   • Handle '.' Character: When encountering a ., simply move to the next character in both the string s and the pattern p.
   • End Condition: Ensure that by the end of the traversal, all characters of s are matched and p is completely considered. If p ends in a '*', it can also end the match as it is capable of matching an empty sequence.

The shifting nuances of '*' necessitating different amounts of backtrack and lookahead in the string make this an intriguing problem, often solved using dynamic programming or recursive algorithms to consider all potential matches meticulously. The constraints provided ensure that the solutions are computationally feasible even with the more complex methods such as recursion with memoization.

Solutions

class Solution {
    public boolean stringMatches(String str, String pat) {
        boolean[][] result = new boolean[str.length() + 1][pat.length() + 1];
        result[str.length()][pat.length()] = true;
    
        for (int i = str.length(); i >= 0; i--) {
            for (int j = pat.length() - 1; j >= 0; j--) {
                boolean initMatch =
                    (i < str.length() &&
                        (pat.charAt(j) == str.charAt(i) ||
                            pat.charAt(j) == '.'));
                if (j + 1 < pat.length() && pat.charAt(j + 1) == '*') {
                    result[i][j] = result[i][j + 2] || (initMatch && result[i + 1][j]);
                } else {
                    result[i][j] = initMatch && result[i + 1][j + 1];
                }
            }
        }
        return result[0][0];
    }
}