LeetCode 139: Word Break, Starting from Prefix Reachability
Problem Input and Output Input: a string s and a list of strings wordDict Every element in wordDict is an available word, and the same word may be reused Output: return True if s can be split into one or more dictionary words; otherwise, return False The split must cover the entire string without skipping or reordering characters Examples Input: s = "leetcode", wordDict = ["leet", "code"] Output: True Explanation: "leetcode" can be split into "leet" + "code" Input: s = "applepenapple", wordDict = ["apple", "pen"] Output: True Explanation: "apple" + "pen" + "apple"; the same word may be reused Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] Output: False Explanation: some prefixes can be formed, but the split cannot cover the entire string Constraints 1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s and wordDict[i] contain only lowercase English letters All strings in wordDict are unique Step 1: Make the Completed Prefix Visible Start with one concrete question. For s = "leetcode", before deciding whether the whole string can be split, can we record how much of it has already been completed? ...