Missing Space Problem

Given a string (all space removed from this) and a dictionary, design an algorithm to add space in ths string in a way that minimizes the number of unrecognized characters.

Algorithm:

1. Call recursive method with original_string, start_index = 0 and empty memo (as cache)
   1. if start_index >= original_string.length then
      1. return bestInvalidChar = 0 and bestParsing = “”
   2. else if memo contain index then return from memo
   3. Set partial = “”, bestInvalidChar = INFINITY and bestParsing = null
   4. Iterate from start_index to end of string
      1. Add current index character of original_string to partial
      2. Check partial_string is in dictionary or not
      3. update invalid_char based on availability of partial in dictionary
      4. if invalid_char is less than bestInvalidChar then explore recursively all next substring
         1. Update bestInvalidChar and bestParsing based on recursive call
   5. Update memo (i.e. cache)
   6. Return result

Latest Source Code:
Github: MissingSpace.java

Output:

 it is a cat