Segment a String into Dictionary Words

Given a continuous lowercase-English string s with no spaces and a helper function: boolean isWord(String str) isWord(str) returns true if and only if str is a valid dictionary word. Use backtracking to split s into valid dictionary words and return any one valid segmentation. The returned array of words must concatenate to exactly s. You may assume that s has at least one valid segmentation, and character order cannot be changed. Example s = "myhousehavecat" One valid output is: ["my", "house", "have", "cat"] Constraints 1 <= len(s) <= 300 A single isWord(word) call may be treated as O(1), but the number of calls should be minimized. Example Input myhousehavecat 8 my house have cat myhouse ha vecat other Output my house have cat