Word Break

medium

Unknown

Question Solve Solutions

1. You are given n space-separated strings, which represents a dictionary of words.
2. You are given another string that represents a sentence.
3. You have to determine if this sentence can be segmented into a space-separated sequence of one or more dictionary words.

Input Format

A number n n strings representing words A string representing a sentence

Output Format

Check the sample ouput and question video.

Constraints

1 &lt;= number of words &lt;= 10
1 &lt;= length of each word &lt;= 15
1 &lt;= length of sentence &lt;= 1000

Example

Input

2
pep coding
pepcoding

Output

true

Print In Range - Bst

Related Questions

easy Is Prime easy Prime Till N easy Reverse Integer easy GCD easy Fibonacci easy Fib Till N easy Exit Point of a matrix easy Placing N Queen in a matrix easy Arranging Vowels And Consonants easy Addition Of Two Linked List easy Circular Linked List easy Sort The Absolute List easy Decimal Number From Binary Linked List easy Find the largest rectangle in a matrix easy Count Pairs Having Sum X easy Delete alternate nodes of linked list