/*
 * 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.problem35;

/**
 * Given an array of strings, can you write a method to return return just words that matches with
 * a pattern containing the "*" regular expression.
 *
 * @author Pedro Vicente Gómez Sánchez.
 */
public class AsteriskRegularExpression {

  public String[] evaluate(String[] words, String pattern) {
    return new String[0];
  }
}

@@ -645,16 +645,69 @@
 lem35;%0A%0A
+import java.util.LinkedList;%0Aimport java.util.List;%0A%0A
 /**%0A * G
@@ -948,92 +948,1698 @@
 %0A%0A  
-public String%5B%5D evaluate(String%5B%5D words, String pattern) %7B%0A    return new String%5B0%5D;
+/**%0A   * Combination of iterative and recursive approaches to resolve this problem. The complexity%0A   * order in time terms is O(N*M) where N is the number of elements in the input array and M the%0A   * size of the word in the array. In space terms, the complexity order of this algorithm is O(N)%0A   * because we are using an additional data structure to store the result.%0A   */%0A  public String%5B%5D evaluate(String%5B%5D words, String pattern) %7B%0A    if (words == null %7C%7C pattern == null) %7B%0A      throw new IllegalArgumentException(%22You can't use null instances as input.%22);%0A    %7D%0A%0A    List%3CString%3E result = new LinkedList%3CString%3E();%0A    for (String word : words) %7B%0A      if (matchAsteriskRegularExpression(word, pattern)) %7B%0A        result.add(word);%0A      %7D%0A    %7D%0A    return result.toArray(new String%5Bresult.size()%5D);%0A  %7D%0A%0A  /**%0A   * The complexity order of this algorithm is more than O(N) but I don't know how to calculate it%0A   * using this recursive version. Is O(N) approximately.%0A   */%0A  private static boolean matchAsteriskRegularExpression(String word, String pattern) %7B%0A    if (word.isEmpty() && pattern.isEmpty()) %7B%0A      return true;%0A    %7D else if (word.isEmpty() %7C%7C pattern.isEmpty()) %7B%0A      return false;%0A    %7D else if (pattern.charAt(0) == '*') %7B%0A      boolean matchRestOfWord = matchAsteriskRegularExpression(word.substring(1), pattern);%0A      boolean matchRestOfPattern = matchAsteriskRegularExpression(word, pattern.substring(1));%0A      return matchRestOfWord %7C%7C matchRestOfPattern;%0A    %7D else %7B%0A      boolean partialMatch = word.charAt(0) == pattern.charAt(0);%0A      return partialMatch && matchAsteriskRegularExpression(word.substring(1),%0A          pattern.substring(1));%0A    %7D
 %0A  %7D

Add solution to problem 35 based on an iterative and recursive approach