一个指针指向 s = "future" 这个字符串的下标 idx,初始从 0 开始。
按字符串输入的顺序来枚举每个输入的字符串,这个字符串中存在 s[idx] 这个字符,则 idx++ ,否则继续枚举下一个字符串。
如果 idx==6,即 s 这个串的所有字符都可以在输入的字符串中按输入顺序在每个字符串中找到一个对应字符,那么就说明可以找到这么一个子序列,否则遍历完所有输入的字符串,idx 仍然小于 6 ,说明找不到。
时间复杂度:O(nm)
一位研究员发现了 n 块从上到下整齐排列的石板,每块石板上刻着一条长度为 m 的小写字母序列。他想从这些石板中按顺序依次选取若干个字符,每块石板至多选取一个,使得这些字符依次形成暗号 tazige。选取时可以跳过若干块石板。请判断是否存在这样的选取方案。保证 n 和 m 均为不超过 1000 的正整数,所有字符均为小写英文字母。
第一行包含两个整数 n 和 m,分别表示石板数量和每块石板上字母序列的长度。保证 n 和 m 均为不超过 1000 的正整数。
接下来 n 行,每行包含一个长度为 m 的字符串,依次表示从上到下各块石板上的字母序列。
输出 Yes 表示存在选取方案可以形成暗号 tazige,否则输出 No。
In following contests:
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.