题目描述

给你一个字符串 $s$ 和一个字符串列表 $wordDict$ 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 $s$ 则返回 $\text{true}$。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

输入格式

第一行一个整数 $T$（$1 \le T \le 10$），表示测试数据组数。

对于每组测试数据：

• 第一行：一个字符串 $s$，仅由小写英文字母组成，长度满足 $1 \le |s| \le 300$。
• 第二行：一个正整数 $n$，表示字典中单词的数量，满足 $1 \le n \le 1000$。
• 接下来 $n$ 行：每行一个字符串 $wordDict_i$，仅由小写英文字母组成，长度满足 $1 \le |wordDict_i| \le 20$，且所有 $wordDict_i$ 互不相同。

输出格式

对于每组测试数据，输出一行，为布尔值 $\text{true}$ 或 $\text{false}$，表示是否能用字典中的单词拼接出字符串 $s$。

样例 #1

样例输入 1

3
leetcode
2
leet
code
applepenapple
2
apple
pen
catsandog
5
cats
dog
sand
and
cat

样例输出 1

true
true
false

样例解释 1

• 第一组数据：leetcode 可以由 leet 和 code 拼接成，返回 $\text{true}$。
• 第二组数据：applepenapple 可以由 apple、pen、apple 拼接成，返回 $\text{true}$，可重复使用字典单词。
• 第三组数据：无法用字典中单词拼接出 catsandog，返回 $\text{false}$。

说明/提示

• $1 \le T \le 10$
• $1 \le s.\text{length} \le 300$
• $1 \le wordDict.\text{length} \le 1000$
• $1 \le wordDict[i].\text{length} \le 20$
• $s$ 和 $wordDict[i]$ 仅由小写英文字母组成
• $wordDict$ 中的所有字符串互不相同