### 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:

- Call recursive method with original_string, start_index = 0 and empty memo (as cache)
- if start_index >= original_string.length then
- return bestInvalidChar = 0 and bestParsing = “”

- else if memo contain index then return from memo
- Set partial = “”, bestInvalidChar = INFINITY and bestParsing = null
- Iterate from start_index to end of string
- Add current index character of original_string to partial
- Check partial_string is in dictionary or not
- update invalid_char based on availability of partial in dictionary
- if invalid_char is less than bestInvalidChar then explore recursively all next substring
- Update bestInvalidChar and bestParsing based on recursive call

- Update memo (i.e. cache)
- Return result

- if start_index >= original_string.length then

Latest Source Code:

Github: MissingSpace.java

**Output:**

it is a cat