2026 华为OD机试真题8月30日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

给定一个mxn的二维字符网格board 和一个字符串单词word。

请计算单词word在网格中出现的总次数。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个搜索路径中不允许被重复使用。

2026 华为OD机试真题8月30日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

输入描述

bord:二维字符列表，每个元素为大写英文字母，1≤m,n≤10。

word:字符串，由大写英文字母组成，1≤len(word)≤100。

输出描述

返回一个整数，表示单词在网格中出现的路径总数。

示例1

输入

[[A,B,C,E],[S,F,C,S],[A,D,E,E]]
ABCCED

输出

1

示例2

输入

[[A,A]]
A

输出

2

说明

网格中有两个 'A'，每个都可以独立构成单词 A，共 2 条路径。

示例3

输入

[[A,B],[C,D]]
ABCD

输出

说明

由于单词必须通过水平相邻或垂直相邻的单元格构成，导致 B 无法直接与 C 构成单词，所以网格中不存在 "ABCD" 的单词路径。

解题思路

核心思想

这是一道网格回溯搜索题。枚举每个可能作为单词首字母的位置，然后从该位置开始按上下左右四个方向继续匹配。搜索过程中用 visited 标记当前路径已经使用过的格子，保证同一条路径不会重复使用同一个单元格。

算法步骤

1. 解析输入的二维字符网格和目标单词。
2. 统计网格中字母数量，如果某个目标字母数量不足，直接返回 0。
3. 枚举每个格子，若它等于 word[0]，则从这里开始 DFS。
4. DFS 当前匹配到 word[index]：
   • 若当前位置字符不匹配，返回。
   • 若 index 已经到达单词最后一个字符，说明找到一条路径，答案加 1。
   • 否则向上下左右四个方向扩展，跳过越界和已经访问过的格子。
5. 输出路径总数。

复杂度分析

设网格大小为 m*n，单词长度为 L。

• 时间复杂度：最坏为 O(m*n*4^L)，实际搜索会被边界、访问标记和字符匹配剪枝减少。
• 空间复杂度：O(m*n + L)，主要来自访问数组和