Regular Expression Matching

描述

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

The function prototype should be:

  1. bool isMatch(const char *s, const char *p)

Some examples:

  1. isMatch("aa","a") → false
  2. isMatch("aa","aa") → true
  3. isMatch("aaa","aa") → false
  4. isMatch("aa", "a*") → true
  5. isMatch("aa", ".*") → true
  6. isMatch("ab", ".*") → true
  7. isMatch("aab", "c*a*b") → true

分析

这是一道很有挑战的题。

递归版

  1. // Regular Expression Matching
  2. // Time complexity: O(n)
  3. // Space complexity: O(1)
  4. class Solution {
  5.     public boolean isMatch(final String s, final String p) {
  6.         return isMatch(s, 0, p, 0);
  7.     }
  8.     private static boolean matchFirst(String s, int i, String p, int j) {
  9.         if (j == p.length()) return i == s.length();
  10.         if (i == s.length()) return j == p.length();
  11.         return p.charAt(j) == '.' || s.charAt(i) == p.charAt(j);
  12.     }
  13.     private static boolean isMatch(String s, int i, String p, int j) {
  14.         if (j == p.length()) return i == s.length();
  16.         // next char is not '*', then must match current character
  17.         final char b = p.charAt(j);
  18.         if (j == p.length() - 1 || p.charAt(j + 1) != '*') {
  19.             if (matchFirst(s, i, p, j)) return isMatch(s, i + 1, p, j + 1);
  20.             else return false;
  21.         } else { // next char is '*'
  22.             if (isMatch(s, i, p, j+2)) return true;  // try the length of 0
  23.             while (matchFirst(s, i, p, j))  // try all possible lengths 
  24.                 if (isMatch(s, ++i, p, j+2)) return true;
  25.             return false;
  26.         }
  27.     }
  28. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/string/regular-expression-matching.html