title: Number of ways to recreate a given string using a given list of words
body: <p>Given is a String <code>word</code> and a String array <code>book</code> that contains some strings. The program should give out the number of possibilities to create <code>word</code> only using elements in <code>book</code>. An element can be used as many times as we want <strong><em>and the program must terminate in under 6 seconds</em></strong>. </p>
  
  <p>For example, input:</p>
  
  <pre><code>String word = "stackoverflow";
  
  String[] book = new String[9];
  book[0] = "st";
  book[1] = "ck";
  book[2] = "CAG";
  book[3] = "low";
  book[4] = "TC";
  book[5] = "rf";
  book[6] = "ove";
  book[7] = "a";
  book[8] = "sta";
  </code></pre>
  
  <p>The output should be <code>2</code>, since we can create <code>"stackoverflow"</code> in two ways: </p>
  
  <p>1: <code>"st"</code> + <code>"a"</code> + <code>"ck"</code> + <code>"ove"</code> + <code>"rf"</code> + <code>"low"</code></p>
  
  <p>2: <code>"sta"</code> + <code>"ck"</code> + <code>"ove"</code> + <code>"rf"</code> + <code>"low"</code></p>
  
  <p>My implementation of the program only terminates in the required time if <code>word</code> is relatively small (&lt;15 characters). However, as I mentioned before, the running time limit for the program is 6 seconds and it should be able to handle very large <code>word</code> strings (>1000 characters). <a href="https://pastebin.com/raw/TPq9aFLj" rel="nofollow noreferrer">Here</a> is an example of a large input. </p>
  
  <p>Here is my code:</p>
  
  <p>1) the actual method:</p>
  
  <p>input: a String <code>word</code> and a String[] <code>book</code></p>
  
  <p>output: the number of ways word can be written only using strings in book</p>
  
  <pre><code>public static int optimal(String word, String[] book){
      int count = 0;
  
      List&lt;List&lt;String&gt;&gt; allCombinations = allSubstrings(word);
  
      List&lt;String&gt; empty = new ArrayList&lt;&gt;();
  
      List&lt;String&gt; wordList = Arrays.asList(book);
  
      for (int i = 0; i &lt; allCombinations.size(); i++) {
  
          allCombinations.get(i).retainAll(wordList);
  
          if (!sumUp(allCombinations.get(i), word)) {
              allCombinations.remove(i);
              allCombinations.add(i, empty);
          }
          else count++;
      }
  
      return count;
  }
  </code></pre>
  
  <p>2) allSubstrings():</p>
  
  <p>input: a String <code>input</code> </p>
  
  <p>output: A list of lists, each containing a combination of substrings that add up to input</p>
  
  <pre><code>static List&lt;List&lt;String&gt;&gt; allSubstrings(String input) {
  
      if (input.length() == 1) return Collections.singletonList(Collections.singletonList(input));
  
      List&lt;List&lt;String&gt;&gt; result = new ArrayList&lt;&gt;();
  
      for (List&lt;String&gt; temp : allSubstrings(input.substring(1))) {
  
          List&lt;String&gt; firstList = new ArrayList&lt;&gt;(temp);
          firstList.set(0, input.charAt(0) + firstList.get(0));
          if (input.startsWith(firstList.get(0), 0)) result.add(firstList);
  
          List&lt;String&gt; l = new ArrayList&lt;&gt;(temp);
          l.add(0, input.substring(0, 1));
          if (input.startsWith(l.get(0), 0)) result.add(l);
      }
  
      return result;
  }
  </code></pre>
  
  <p>3.) sumup():</p>
  
  <p>input: A String list <code>input</code> and a String <code>expected</code></p>
  
  <p>output: true if the elements in <code>input</code> add up to <code>expected</code></p>
  
  <pre><code>public static boolean sumUp (List&lt;String&gt; input, String expected) {
  
      String x = "";
  
      for (int i = 0; i &lt; input.size(); i++) {
          x = x + input.get(i);
      }
      if (expected.equals(x)) return true;
      return false;
  }
  </code></pre>