小美的子序列
美团 2023-09-02 笔试编程题（每题 20 分）
题目描述
小美在 n 行 m 列的本子上写了许多字母，她会在每一行中找出一个字母，
然后按行序组成一个字符串。小美想知道，组成的字符串中是否存在至少一个
包含 meituan 子序列的字符串。
输入格式
第一行两个整数 n、m（1 ≤ n, m ≤ 1000）。 接下来 n 行，每行一个长度为 m 的字符串，表示小美写下的字母。
输出格式
若存在至少一个字符串包含 meituan 子序列，则输出 YES，否则输出 NO。
示例
示例 1
输入：
3 3
abc
def
ghi
输出：
NO
说明：
三行里都找不到 m，凑不出 meituan，输出 NO。
示例 2
输入：
8 2
nm
ex
it
td
ul
qu
ac
nt
输出：
YES
说明：
依次从第 1~5、7、8 行取出 m e i t u a n，组成的字符串里含有
meituan 子序列。
解题思路
第一步：看清「怎么组字符串」
每一行只能出一个字母，而且组出来的字符串的顺序就是行的顺序。 所以问题等价于：
能否在第 1、2、…、n 行中，依次找到
m、e、i、t、u、a、n， 每个字符来自不同的行，且行的次序与字符次序一致？
第二步：暴力枚举（会爆炸）
每行有 m 种选法，共 n 行，暴力枚举是 m^n 种，根本不可行。
第三步：双指针贪心（推荐）
从需要的第一个字符 m 开始，自上而下扫每一行：
- 如果这一行里出现了「当前需要的字符」，就把它匹配掉、指针后移一位；
- 否则跳过这一行。
扫完所有行后，如果 7 个字符都匹配到了，就输出 YES。
为什么贪心是对的？ 越早匹配掉当前字符，后面可用的行就越多； 故意晚匹配只会让后面的选择更少，不会更好。这正是子序列匹配的标准贪心。
完整代码实现
算法可视化 · 逐帧回放这道题的代码6 帧 · 录制输入
import sys
TARGET = "meituan"
def solve() -> None:
"""每行匹配一个目标字符，能匹配完就 YES"""
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
rows = data[2:2 + n] # 第 2 个整数是列数 m，逐行匹配时用不到
idx = 0
for row in rows:
if idx < len(TARGET) and TARGET[idx] in row:
idx += 1
sys.stdout.write("YES\n" if idx == len(TARGET) else "NO\n")
if __name__ == "__main__":
solve()
示例推演
以示例 2 为例，目标 meituan：
| 行 | 内容 | 需要匹配 | 是否命中 | 指针 |
|---|---|---|---|---|
| 1 | nm | m | 是 | 1 |
| 2 | ex | e | 是 | 2 |
| 3 | it | i | 是 | 3 |
| 4 | td | t | 是 | 4 |
| 5 | ul | u | 是 | 5 |
| 6 | qu | a | 否 | 5 |
| 7 | ac | a | 是 | 6 |
| 8 | nt | n | 是 | 7 |
指针到达 7（长度），输出 YES。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 暴力枚举 | O(m^n) | O(n) | 不可行 |
| 双指针贪心 | O(n · m) | O(1) | 推荐 |
每行用一次
in判断是否含某字符，单次 O(m)。
易错点总结
1. 以为可以在一行里取多个字母
每行只能出一个字母，所以匹配到的字符必须分布在不同行。
2. 顺序搞反
行的顺序就是字符串的顺序，因此必须自上而下依次匹配 meituan，
不能回头再去前面的行取字符。
3. 输出大小写
题目要求输出 YES / NO（全大写）。
扩展思考
- 若允许每行取任意多个字母，就退化成「整个矩阵里是否有 meituan 子序列」， 简单扫描即可。
- 若目标串很长、行数很多，仍是同一套贪心，复杂度不变。