package general;

public class RegexMatching {

	public static boolean matchRegex(String str, String regex) {
		if (str == null || regex == null) {
			return false;
		}

		return matchRegex(str, 0, regex, 0);
	}

	private static boolean matchRegex(String str, int strIndex, String regex,
			int regexIndex) {
		if (strIndex >= str.length() && regexIndex == regex.length()) {
			return true;
		}

		if (regexIndex == regex.length()) {
			return false;
		}

		char regexChar = regex.charAt(regexIndex);

		if (regexIndex < regex.length() - 1) {
			char nextRegexChar = regex.charAt(regexIndex + 1);
			if (nextRegexChar == '*') {
				// Check if we could skip this wild card and still match the
				// regex.
				if (matchRegex(str, strIndex, regex, regexIndex + 2)) {
					return true;
				}

				// We could have clubbed the two for loops below into one,
				// but having a separate loop for the '.' character prevents
				// checking of the matching condition for every iteration,
				// because '.' matches any character. For 1,2,...,N
				// possible occurrences of the '.' character, we
				// recursively check if there is a regex match.
				if (regexChar == '.') {
					for (int wildCardMatcher = strIndex; wildCardMatcher < str
							.length(); wildCardMatcher++) {
						if (matchRegex(str, wildCardMatcher + 1, regex,
								regexIndex + 2)) {
							return true;
						}
					}
				}

				// For 1,2,...,N possible occurrences of the current regex
				// character, we recursively check if there is a regex match.
				for (int wildCardMatcher = strIndex; wildCardMatcher < str
						.length() && str.charAt(wildCardMatcher) == regexChar; wildCardMatcher++) {
					if (matchRegex(str, wildCardMatcher + 1, regex,
							regexIndex + 2)) {
						return true;
					}
				}

				return false;
			}
		}

		if (regexChar == '*') {
			throw new RuntimeException("Invalid regex input.");
		}

		// We need a concrete match for a single character now before we
		// recursively check the rest. So if there are no more characters left,
		// we bail out.
		if (strIndex >= str.length()) {
			return false;
		}

		if (regexChar == '.') {
			return matchRegex(str, strIndex + 1, regex, regexIndex + 1);
		}

		if (regexChar == str.charAt(strIndex)) {
			return matchRegex(str, strIndex + 1, regex, regexIndex + 1);
		}

		return false;
	}
}

@@ -11,16 +11,502 @@
 neral;%0A%0A
+/**%0A * Write a function to match a given string to a regular expression.%0A * %0A * '.' Matches any single character.%0A * '*' Matches zero or more of the preceding element.%0A * %0A * The matching should cover the entire input string (not partial).%0A * %0A * Some examples:%0A *  isMatch(%22aa%22,%22a%22) %E2%86%92 false%0A *  isMatch(%22aa%22,%22aa%22) %E2%86%92 true%0A *  isMatch(%22aaa%22,%22aa%22) %E2%86%92 false%0A *  isMatch(%22aa%22, %22a*%22) %E2%86%92 true%0A *  isMatch(%22aa%22, %22.*%22) %E2%86%92 true%0A *  isMatch(%22ab%22, %22.*%22) %E2%86%92 true%0A *  isMatch(%22aab%22, %22c*a*b%22) %E2%86%92 true%0A */%0A
 public c
@@ -546,34 +546,31 @@
 tic boolean 
-m
+isM
 atch
-Regex
 (String str,
@@ -651,34 +651,31 @@
 %7D%0A%0A%09%09return 
-m
+isM
 atch
-Regex
 (str, 0, reg
@@ -710,26 +710,23 @@
 boolean 
-m
+isM
 atch
-Regex
 (String 
@@ -1181,34 +1181,31 @@
 ex.%0A%09%09%09%09if (
-m
+isM
 atch
-Regex
 (str, strInd
@@ -1748,34 +1748,31 @@
 %7B%0A%09%09%09%09%09%09if (
-m
+isM
 atch
-Regex
 (str, wildCa
@@ -2145,26 +2145,23 @@
 %09%09%09%09if (
-m
+isM
 atch
-Regex
 (str, wi
@@ -2606,34 +2606,31 @@
 %7B%0A%09%09%09return 
-m
+isM
 atch
-Regex
 (str, strInd
@@ -2723,18 +2723,15 @@
 urn 
-m
+isM
 atch
-Regex
 (str

Add comments for regex matching.