LeetCode Q139 Word Break

Q139 Word Break



 Take catsandog as example
 We start to check if we can break the substring from the last char 'g', then 'og', 'dog', and we need to record the places we can break.
 So when we look at the longer string, we can reuse the results from a previous round

 Check if we find wordDic contains in this order
 g      - g: NO
 og     - o:  NO
        - og:  NO
 dog    - d: NO
        - do:   NO
        - dog:  Yes, but we can only break when we can cut at the place before dog and after dog, in this case YES, since
 ndog   continues.....
 ...
 andog  - ...
        - and: Yes, wordDic contains 'and', however because from the previous rounds, we can not cut d|o, so we can not cut before a, like |andog

 catsandog - finally, we will end with we cannot cut just before 'c', that is the result of the whole string. because we can not break like cat|sandog

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q139WordBreak.playground/Contents.swift