Word Break Problem

Given a string `s` and a dictionary of strings `wordDict`, return `true` if `s` can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation. ### Constraints - `1 <= s.length <= 300` - `1 <= wordDict.length <= 1000` - `1 <= wordDict[i].length <= 20` - `s` and `wordDict[i]` consist of only lowercase English letters. - All strings of `wordDict` are unique. ### Input Format First line contains the string `s`. Second line contains integer `k` representing number of words in dictionary. Third line contains `k` space-separated words in `wordDict`. ### Output Format Print `true` if `s` can be segmented, otherwise `false`.