线性动态规划：单词搜索 II 的变种——带方向限制的单词搜索

题目描述

我们有一个 m x n 的字符网格 board 和一个单词列表 words。
你需要在网格中找出所有在列表中出现的单词。
额外限制：
每个单词必须从某个单元格开始，沿着上、下、左、右四个方向之一直线延伸（即不能转弯）来构成，且每个单元格在同一个单词中最多使用一次。
请你返回所有能在网格中找到的单词，按字典序排序。

示例：

board = [
  ['a', 'b', 'c'],
  ['d', 'e', 'f'],
  ['g', 'h', 'i']
]
words = ["abc", "aei", "beh", "cfi", "def", "ghi", "adg", "be", "cf"]

输出：

["abc", "aei", "beh", "cfi", "def", "ghi", "adg", "be", "cf"]

解释：

• "abc" 在第一行从左到右。
• "aei" 从 (0,0) 向右下对角线延伸，但注意：题目限制只有上下左右四个方向，没有斜向，所以这里实际上应该只考虑四个正交方向。但在本例中，假设方向限制仅为“上、下、左、右直线延伸”，那么 "aei" 是找不到的（除非网格允许斜向）。这里为了举例清晰，假设题目允许单个方向的直线延伸，包括八个方向（常见变种），但为简化，我们按四个正交方向来设计题目。
  为了示例合理性，我们把示例改为：

board = [
  ['a', 'b', 'c'],
  ['d', 'e', 'f'],
  ['g', 'h', 'i']
]
words = ["abc", "beh", "cfi", "adg", "be", "cf"]

输出：

["abc", "beh", "cfi", "adg", "be", "cf"]

• "abc" 第一行水平向右。
• "beh" 从 (0,1) 垂直向下得到 b(0,1) → e(1,1) → h(2,1)。
• 其余类似。

解题思路

这个问题是“单词搜索 II”（Leetcode 212）的简化变种，因为单词只能在一个方向延伸，不能转弯，且每个单元格只能用一次。
这反而简化了搜索，因为我们只需要对每个起点、每个方向，尝试延伸长度 1 到最大单词长度，判断形成的字符串是否在单词集中即可。

步骤详解

第一步：问题理解与模型转换

1. 对于每个起点 (r, c)，有四个方向：上下左右。
2. 对每个方向，我们从起点开始，沿着这个方向走 len 步（len 从 1 到单词最大长度，且不能出界，且不重复使用单元格——但这里由于是直线且不转弯，所以不会重复使用单元格，除非重复经过同一格，但直线延伸不会走回已走过的格，因为方向固定）。
3. 将沿途字符拼接成字符串，如果在单词集合中，就加入结果。
4. 结果去重并按字典序排序。

第二步：数据结构选择

1. 单词列表用哈希集合 wordSet 存储，便于 O(1) 查询。
2. 结果用哈希集合 found 存储，避免重复。
3. 方向数组：dirs = [(0,1),(1,0),(0,-1),(-1,0)] 对应右、下、左、上。

第三步：动态规划/预处理优化

由于单词可以出现在任意起点、任意方向、任意长度，我们可以预处理：

• 对每个起点 (r, c)，对每个方向 (dr, dc)，从该点出发，生成所有可能的字符串（长度 1 到出界为止）。
• 检查这些字符串是否在单词集合中。

复杂度分析：

• 起点数：m*n
• 方向数：4
• 最大长度：max_len（单词最大长度）
• 每个方向最多延伸 max_len 步（或到边界为止）。
• 总检查次数：O(m*n*4*max_len)，每次生成字符串可逐步累加字符，O(1) 追加字符并检查。

注意：我们并不需要传统“单词搜索 II”的 Trie 树回溯，因为这里路径是直线，不会分叉，所以直接枚举并检查即可。

第四步：算法步骤

1. 将 words 存入哈希集合 wordSet，并记录最大单词长度 max_len。
2. 初始化结果集合 found。
3. 遍历每个起点 (r, c)：
   • 对四个方向 (dr, dc)：
     • 初始化当前字符串 s = ""
     • 从起点开始，沿着方向走 k 步（k=0,1,...,max_len-1）：
       • 计算新位置 nr = r + k*dr, nc = c + k*dc
       • 如果越界则停止延伸
       • s += board[nr][nc]
       • 如果 s 在 wordSet 中，加入 found
4. 将 found 转为列表，排序，返回。

第五步：边界与去重

• 同一个单词可能从不同起点或不同方向找到多次，用集合去重。
• 单词长度可能为 1，要包含。
• 网格中字母可重复，但路径是直线，不会重复使用同一单元格（因为每一步都是新位置，除非网格很小但方向导致走回，但我们限制方向向量固定，不会走回，因为 k 递增，位置线性变化）。

第六步：示例推演

以示例简单推演：

board = [
  ['a','b','c'],
  ['d','e','f'],
  ['g','h','i']
]
words = ["abc","beh","cfi","adg","be","cf"]

起点 (0,0)，方向右 (0,1)：

• k=1: "a" 不在集合
• k=2: "ab" 不在
• k=3: "abc" 在，加入 found

起点 (0,1)，方向下 (1,0)：

• k=1: "b" 不在
• k=2: "be" 在，加入
• k=3: "beh" 在，加入

... 以此类推，最后 found = {"abc","beh","cfi","adg","be","cf"}，排序后输出。

第七步：复杂度

• 时间：O(m * n * 4 * max_len)，因为每个起点每个方向最多走 max_len 步。
• 空间：O(total_word_length) 用于存单词集合和结果。

第八步：进一步优化

如果单词列表很大，可以用前缀集合优化：
在延伸字符串时，如果当前字符串不是任何单词的前缀，可以提前终止延伸，因为再延伸也不会匹配任何单词。
这需要将单词列表的所有前缀存入哈希集合 prefixSet。
延伸时，若 s 不在 prefixSet 中，则 break。

总结

本题虽然是单词搜索 II 的变种，但因限制为直线方向，避免了复杂回溯，只需枚举所有直线路径并检查是否在单词集合中，利用哈希集合或前缀集合加速查询即可。