In cooking terms, a recipe is a prep-list combination of ingredients if you can prepare it by joining together the first several ingredients from the array, one after another, starting from the very beginning.
More formally, a string recipe is a prep-list combination of an array of strings ingredients if there exists some index i >= 0 such that:
recipe = ingredients[0] + ingredients[1] + ... + ingredients[i]Example:
- For
ingredients = ["flour", "sugar", "eggs"],"flour"is a prep-list combination. "floursugar"is also a prep-list combination."floursug"is not a prep-list combination."floureggs"is not a prep-list combination.
Task: Given two arrays of strings ingredients and recipes, determine for each recipe whether it is a prep-list combination of ingredients. Return an array of booleans of length recipes.length, where the i-th element is true if recipes[i] matches, and false otherwise.
Note: A solution with time complexity not worse than O(ingredients.length^2 * recipes.length) will fit within the execution time limit.
这道题本质上是在判断每个 recipe 是否等于 ingredients 从第 0 个元素开始、按顺序依次拼接出来的某个前缀字符串。做法上可以先把 ingredients 的前缀拼接结果逐步构造出来，再对每个 recipe 做一次前缀匹配判断；因为只允许从开头连续取若干项，所以不是任意子序列或任意拼接都算。样例里像 "flour"、"floursugar" 都是合法前缀，而 "sugarflour" 虽然能由两个字符串拼出来，但顺序不对、也不是从第一项开始连续拼接，因此返回 false。整体难点在于理解“从头连续拼接”的约束，数据结构上只需要字符串累积和逐个比较即可。
