在LeetCode 79题“单词搜索”中，给定一个二维字符矩阵和一个单词列表，判断给定的单词是否存在于矩阵的每一行、每一列或由这些字符构成的任意一条对角线上。我们需要编写一个函数来返回所有满足条件的单词列表。
这道题有多种解法，其中比较常见的是回溯法和位运算优化法。下面我们将分别解析这两种方法的原理和实现。
一、回溯法
回溯法是一种基于试错的算法，通过穷举所有可能的解来找出所有满足条件的解。在解决“单词搜索”问题时，我们可以使用回溯法来枚举所有可能的单词组合，然后判断它们是否满足条件。
具体实现步骤如下：
- 定义一个递归函数，用于生成所有可能的单词组合。在函数中，我们首先判断当前位置是否超出了矩阵范围或者已经选择了其他位置的单词，如果是，则返回空字符串。否则，我们选择当前位置的单词，并递归调用函数生成左上方和右上方两个方向的单词组合。
- 在递归函数中，我们需要判断当前生成的单词是否满足条件。具体来说，我们需要遍历矩阵的每一行、每一列和对角线，判断当前单词是否出现在这些方向上。如果出现，则将当前单词加入结果列表中，并继续生成其他方向的单词组合。
- 在主函数中，我们首先遍历矩阵中的每个字符，然后调用递归函数生成以该字符为起点的所有可能单词组合。最后返回结果列表。
二、位运算优化法
位运算优化法是一种基于位运算的算法，通过将矩阵中的每个字符映射到一个整数，利用位运算来高效地判断一个单词是否满足条件。
具体实现步骤如下： - 定义一个位运算数组，用于记录矩阵中每个字符的出现情况。数组的长度为26，下标对应字母的ASCII码减去字母’a’的ASCII码。数组的值表示相应字母在矩阵中出现的次数。
- 在主函数中，我们首先遍历矩阵中的每个字符，更新位运算数组。然后遍历每个单词，对于每个单词的每个字符，判断它在矩阵中的出现次数是否与位运算数组中的值匹配。如果匹配，则将该单词加入结果列表中。
- 在判断一个字符是否匹配时，我们可以通过按位与运算来判断该字符在矩阵中的出现次数是否包含在位运算数组的值中。具体来说，我们将位运算数组的值左移对应的位数（即ASCII码减去字母’a’的ASCII码），然后与目标字符进行按位与运算。如果结果为0，则表示目标字符在矩阵中没有出现；如果不为0，则表示目标字符在矩阵中出现过。
通过对比回溯法和位运算优化法，我们可以发现位运算优化法的效率更高。这是因为位运算优化法利用了位运算的高效性，避免了递归调用的开销和大量的重复计算。在实际应用中，我们可以根据具体情况选择合适的算法来解决“单词搜索”问题。