Construct String from Dictionary Words

You are given a string s and a list of words. Your task is to determine whether the string s can be constructed by concatenating words from the given list. Each word in the list may be used multiple times.

The problem can be formalized as follows:

Given a string \( s \) and a list of strings \( W = [w_1, w_2, \dots, w_n] \), determine if there exists a sequence of indices \( i_1, i_2, \dots, i_k \) such that \[ s = w_{i_1} + w_{i_2} + \cdots + w_{i_k} \] where the plus sign denotes string concatenation.

Input/Output instructions: All input is read from standard input (stdin) and all output should be written to standard output (stdout).

inputFormat

The input consists of multiple lines:

• The first line contains the string s.
• The second line contains an integer n representing the number of words in the list.
• The following n lines each contain one word.

outputFormat

Output a single line containing either True or False (without quotes) indicating whether the string s can be constructed from the given list of words.

leetcode
2
leet
code

True