启云方 9.25 笔试：通配符匹配与文件系统模拟

《面试题目》

1. 第一题（100 分）：字符串匹配。? 替换奇数位的字符，* 替换 0 个或多个字符。
2. 第二题（100 分）：实现 linux 的 ls、addfile，用 * 表示输出文件夹，文件直接输出。
3. 第三题（200 分）：给中序遍历和后序遍历序列，输出层序遍历。

《参考解析》

1. 通配符匹配（第一题）：经典的双序列 DP。设 dp[i][j] 表示模式串前 i 个字符能否匹配文本串前 j 个字符。转移分三种情况：模式字符是普通字符，要求 s[i-1] == t[j-1] 且 dp[i-1][j-1]；是 ?（题目限定只匹配奇数位，即按 1 起始的下标为奇数的位置），要求当前位置符合奇数位约束；是 *，则可以匹配 0 个字符（dp[i-1][j]）或匹配一个及以上（dp[i][j-1]）。边界是 dp[0][0]=true，dp[0][j]=false，而模式前缀全为 * 时 dp[i][0]=true。复杂度 O(m·n) 时间、可滚动到 O(n) 空间。要注意题面里”? 替换奇数位的字符”是个特化约束而不是标准通配符——先按题面把约束写进转移条件，别直接套通用的 ? 匹配任意单字符。

2. 模拟 ls / addfile（第二题）：用树结构建模目录。每个节点持有名字、类型（文件 / 目录）和子节点集合（用有序 map 或按名字排序的 list 保证输出顺序稳定）。addfile <path> 按分隔符逐级向下查找或创建目录，最后一级作为文件插入；重复路径要按题面决定是覆盖还是忽略。ls <path> 定位到节点后遍历子节点：目录输出时加 * 前缀（题面用 * 表示文件夹），文件直接输出名字。要点是三处细节：路径分隔与根目录的处理、输出排序规则、以及非法路径（父目录不存在）时的行为——这些边界往往就是得分点。

3. 中序 + 后序 → 层序（第三题）：后序遍历的最后一个元素一定是根，在中序序列里找到它的位置，左边是左子树、右边是右子树，递归构建二叉树；再用队列做 BFS 输出层序遍历。实现上为避免 O(n²) 的反复查找，先用哈希表把中序序列的”值 → 下标”映射建好，递归时按下标区间切分，整体做到 O(n)。同理，中序 + 前序也走这套（前序的首元素是根），但只有前序 + 后序无法唯一确定一棵二叉树——这是常见的追问点。