LeetCode Solutions

			

    class Solution {
        public:
         bool isMatch(string s, string p) {
           const int m = s.length();
           const int n = p.length();
           // dp[i][j] := true if s[0..i) matches p[0..j)
           vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
           dp[0][0] = true;
       
           auto isMatch = [&](int i, int j) -> bool {
             return j >= 0 && p[j] == '.' || s[i] == p[j];
           };
       
           for (int j = 0; j < p.length(); ++j)
             if (p[j] == '*' && dp[0][j - 1])
               dp[0][j + 1] = true;
       
           for (int i = 0; i < m; ++i)
             for (int j = 0; j < n; ++j)
               if (p[j] == '*') {
                 const bool noRepeat = dp[i + 1][j - 1];  // Min index of '*' is 1
                 const bool doRepeat = isMatch(i, j - 1) && dp[i][j + 1];
                 dp[i + 1][j + 1] = noRepeat || doRepeat;
               } else if (isMatch(i, j)) {
                 dp[i + 1][j + 1] = dp[i][j];
               }
       
           return dp[m][n];
         }
       };			 

    class Solution {
        public boolean isMatch(String s, String p) {
          final int m = s.length();
          final int n = p.length();
          // dp[i][j] := true if s[0..i) matches p[0..j)
          boolean[][] dp = new boolean[m + 1][n + 1];
          dp[0][0] = true;
      
          for (int j = 0; j < p.length(); ++j)
            if (p.charAt(j) == '*' && dp[0][j - 1])
              dp[0][j + 1] = true;
      
          for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
              if (p.charAt(j) == '*') {
                final boolean noRepeat = dp[i + 1][j - 1]; // Min index of '*' is 1
                final boolean doRepeat = isMatch(s, i, p, j - 1) && dp[i][j + 1];
                dp[i + 1][j + 1] = noRepeat || doRepeat;
              } else if (isMatch(s, i, p, j)) {
                dp[i + 1][j + 1] = dp[i][j];
              }
      
          return dp[m][n];
        }
      
        private boolean isMatch(final String s, int i, final String p, int j) {
          return j >= 0 && p.charAt(j) == '.' || s.charAt(i) == p.charAt(j);
        }
      }	  

    class Solution:
    def isMatch(self, s: str, p: str) -> bool:
      m = len(s)
      n = len(p)
      # dp[i][j] := True if s[0..i) matches p[0..j)
      dp = [[False] * (n + 1) for _ in range(m + 1)]
      dp[0][0] = True
  
      def isMatch(i: int, j: int) -> bool:
        return j >= 0 and p[j] == '.' or s[i] == p[j]
  
      for j, c in enumerate(p):
        if c == '*' and dp[0][j - 1]:
          dp[0][j + 1] = True
  
      for i in range(m):
        for j in range(n):
          if p[j] == '*':
            noRepeat = dp[i + 1][j - 1]  # Min index of '*' is 1
            doRepeat = isMatch(i, j - 1) and dp[i][j + 1]
            dp[i + 1][j + 1] = noRepeat or doRepeat
          elif isMatch(i, j):
            dp[i + 1][j + 1] = dp[i][j]
  
      return dp[m][n]