Segment Words

Languages

Given a string str and a list of words dict, determine if str can be segmented into a sequence of one or more words from dict. Words from dict can be reused multiple times in the segmentation.

Return true if it is possible to segment str, and false otherwise.

Input

  • str: string: A string representing the string to be segmented
  • dict: string[]: An array of strings representing the dictionary of available words

Notes

  • Words from dict can be used multiple times in the segmentation

Examples

Input: str = "greatfrontendgreat", dict = ["frontend","great"]
Output: true
Explanation: The string can be segmented as 'great' + 'frontend' + 'great' as we can re-use 'great'.
Input: str = "abcd", dict = ["a","abc","b","cd"]
Output: true
Explanation: The string can be segmented as 'a' + 'b' + 'cd'.
Input: str = "a", dict = ["b"]
Output: false
Explanation: The single character 'a' is not in the word dictionary.

Constraints

  • 1 <= str.length <= 300
  • 0 <= dict.length <= 300
  • 0 <= dict[i].length <= 300
  • str and dict[i] consist of only lowercase English letters
zh-CN的翻译是测试版,可能不准确。 如果您有兴趣帮助翻译,请提供反馈或联系我们