Created by Wang, Jerry, last modified on Dec 18, 2015

In getAllPossibleSentences, S: catsanddog pos: 9 Sub String: catsanddog Traverses word in the dictionary one by one to check whether the current substring ends in word. Sub String ends with word in Dict! : dog – Find a match in the dictionary. Current Position: 9 Word Length: 3 First Seg end: 6 Ready to start recursion after finding a match. On-screen shrink Call, New position: 6 in getAllPossibleSentences, S: catsanddog POS: 6 The execution stream will not return at this point, still assuming the current dog match. Sub string: catsand Sub String ends with word in Dict! : Sand current position: 6 Word Length: 4 First Seg end: 2 RECURSIVELY matched New position: 2 in getAllPossibleSentences, s: catsanddog pos: 2 Sub string: cat Sub String ends with word in Dict! Dog -> Sand -> Cat Current position: 2 Word Length: 3 First Seg end: -1 recursion Call, New Position: -1 in getAllPossibleSentences, s: catsanddog pos: -1 pos is -1, we can return now and have a rest! Return result size: 1 – This is the default space result from getAllPossible with position: -1 – Returns one level from the innermost recursion. Result list’s item is string. space, so I directly insert end word to solution list: cat – Add the innermost cat result to the list. Possible solution FOUND:! Cat insert map with position: 2 possible list: 1 [-1, “”] [2, cat] result from getAllPossible with position: 2 item in result list: cat – previous recursive insert Current Word in DIC: SAND – Current recursive frame word. Possible solution FOUND:! cat sand Sub String ends with word in Dict! : and (Sub string: catsand) current position: 6 word length: 3 first Seg end: 3 RECURSIVELY call, new position: 3 in getAllPossibleSentences, s: catsanddog pos: 3 Sub string: cats Sub String ends with word in Dict! : cats current position: 3 word length: 4 first Seg end: -1 RECURSIVELY call, new position: -1 in getAllPossibleSentences, s: catsanddog pos: -1 pos is -1, we can return now and have a rest! return result size: 1 result from getAllPossible with position: -1 item in result list: Current word in dic: Cats result list’s item is string. space, so I directly insert end word to solution list: cats Possible solution FOUND:! cats insert map with position: 3 possible list: 1 result from getAllPossible with position: 3 item in result list: catsCurrent word in dic: and Possible solution FOUND:! cats and insert map with position: 6 possible list: 2 result from getAllPossible with position: 6 item in result list: cat sandCurrent word in dic: dog Possible solution FOUND:! cat sand dog item in result list: cats andCurrent word in dic: dog Possible solution FOUND:! cats and dog insert map with position: 9 possible list: 2 result: cat sand dog result: cats and dog