12 矩阵中的路径

题目

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。

[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

但矩阵中不包含字符串“abfb”的路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入这个格子。

思考

• 我一开始没考虑那么多，直接写了个bfs，运行之前就突然意识到了一种情况
  • [["a","b","c"], ["b","e","g"]], word="abebc"
  • 按照bfs，则可能由于都标记了visited而无法输出正确答案
  • 因此，又要重新写个dfs咯
• dfs，尝试去优化：通过手动提前判断一层，先看是不是相等的再调用，实际上好像并没有很大差别，突然记起以前的c++书？上好像有讲类似的内容
  • 然后删了很多少用的变量，性能依旧很差很差
• 参考别人的解答：
  • 有人不另外开个visited数组而是直接在board上进行非法标识标记
  • 最重要的是！！：别人穿string word的时候，传的是引用，而我传的是值！！！啊啊啊！！加一个符号，性能飞速提升！！！然后就意识到leetcode给的board直接是引用传递，所以我的dfs才是引用传递，否则，我怀疑我会直接TLE
• 前面的错误原因：
  • 提前考虑了一层，而没有考虑word的size为1的情况
  • 没有考虑到 [["a","a"]]， "aaa"的情况，即index>=word.size()的情况应该return false而不是true
• 结果
  • 中间32ms那个是copy别人的代码看看效果怎么样
  • 最终我的居然更好一丢丢！