/*
 * Copyright (C) 2014 Pedro Vicente Gómez Sánchez.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.github.pedrovgs.problem33;

/**
 * Can you write a method to analyze some strings with regular expressions and return true if the
 * expression matches with the word? Expressions supported are:
 * '.' Matches any single character.
 * '*' Matches zero or more of the preceding element.
 *
 * @author Pedro Vicente Gómez Sánchez.
 */
public class SimpleRegularExpression {

  public boolean evaluate(String input, String regularExpression) {
    return false;
  }
}

@@ -995,74 +995,1082 @@
 %0A%0A  
-public boolean evaluate(String input, String regularExpression) %7B%0A
+/**%0A   * Tail recursive solution to this problem. The complexity order of this algorithm is O(N%5E2) in%0A   * time terms and O(1) in space terms because we are not using any additional data structure to%0A   * solve this problem.%0A   */%0A  public boolean evaluate(String source, String pattern) %7B%0A    if (source == null %7C%7C pattern == null) %7B%0A      throw new IllegalArgumentException(%22You can't pass a null strings as input%22);%0A    %7D%0A    if (pattern.length() == 0) return source.length() == 0;%0A    // Length 1 is special case%0A    if (pattern.length() == 1 %7C%7C pattern.charAt(1) != '*') %7B%0A      if (source.length() %3C 1 %7C%7C (pattern.charAt(0) != '.' && source.charAt(0) != pattern.charAt(%0A          0))) %7B%0A        return false;%0A      %7D%0A      return evaluate(source.substring(1), pattern.substring(1));%0A    %7D else %7B%0A      int len = source.length();%0A%0A      int i = -1;%0A      while (i %3C len && (i %3C 0 %7C%7C pattern.charAt(0) == '.' %7C%7C pattern.charAt(0) == source.charAt(%0A          i))) %7B%0A        if (evaluate(source.substring(i + 1), pattern.substring(2))) return true;%0A        i++;%0A      %7D%0A  
     
@@ -2083,14 +2083,20 @@
  false;%0A
+    %7D%0A
   %7D%0A%7D%0A

Add tail recursive solution to problem 33