Word Segmentation with a Dictionary Helper

Algorithm · Amazon · Medium

You are given a string s that contains only lowercase English letters (a–z). A helper function isWord(sub) is available to you: it returns true exactly when the substring sub appears in the dictionary. The dictionary itself is hidden; you may only query it through this function. Your task is to split s into a sequence of valid words, keeping the original order of the characters. Return any one valid segmentation as a list of strings. If the input can be broken in more than…