Word Break

Medium

triedynamic-programmingstringhash-table

Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of one or more dictionary words (words may be reused).

Input

Line 1: the string s
Line 2: space-separated dictionary words

Output: true or false.

Example 1

Input:

leetcode
leet code

Output:

true

Example 2

Input:

applepenapple
apple pen

Output:

true

Example 3

Input:

catsandog
cats dog sand and cat

Output:

false

Constraints

1 ≤ s.length ≤ 300
1 ≤ dictionary size ≤ 1000; lowercase letters.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Word Break

Medium

triedynamic-programmingstringhash-table

Given a string s and a dictionary of words, return true if s can be segmented into a space-separated sequence of one or more dictionary words (words may be reused).

Input

Line 1: the string s
Line 2: space-separated dictionary words

Output: true or false.

Example 1

Input:

leetcode
leet code

Output:

true

Example 2

Input:

applepenapple
apple pen

Output:

true

Example 3

Input:

catsandog
cats dog sand and cat

Output:

false

Constraints

1 ≤ s.length ≤ 300
1 ≤ dictionary size ≤ 1000; lowercase letters.

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.