题目描述

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

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

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

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

输出格式

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

样例

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

true
true
false

样例解释

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

数据范围

• $1 \le T \le 10$
• 字符串 $s$ 的长度满足 $1 \le |s| \le 300$
• 字典中单词数量 $n$ 满足 $1 \le n \le 1000$
• 每个字典单词长度满足 $1 \le |wordDict_i| \le 20$
• 所有字符串仅由小写英文字母组成
• $wordDict$ 中的字符串互不相同