一道题引起的反思

引言

今天中午做一道 Leetcode Mid 级别的题目，一看到题之后就有想法，但是后来沿着错误的想法想了非常久。其实问题本身很简单，如果知道正确思路，大概 3 分钟不到能做出来。

由于做题的过程中，想起一些生活的经历和做事方法，特地来反思一下做题或者平时生活解决问题时，需要注意的一些事情。

467. 环绕字符串中唯一的子字符串

题意大致是: 给一个循环串 $s$ 和字符串 $p$，问字符串 $p$ 的所有子串中，包含于 $s$ 并且本质不同的串的个数

错误想法 1: 枚举 $s+s$ 的所有子串，看看在 $p$ 里面有没有出现，哈希表去重

  • 遗漏了所有长于 $s+s$ 的所有结果
  • 时间复杂度太高

错误想法 2: 把 $p$ 分成很多段，每一段子串都是包含于 $s$ 且最长的。对每一段 $t$ 建模: $t = s[:i] + k * s + s[:j]$，不重地枚举 $t$ 的个数。

  • 想法其实是对的
  • 不重地枚举很难做 (也就是很难考虑非重复子串)

反思: 遇到想法中困难的地方，没有及时地跳出来，另外寻找方法解决，反而越陷越深。快速思考的同时，深度太浅，没有仔细考虑应用场景。

  • 缺乏评估问题复杂度的能力: 自己的能力是否能在限定的时间解决该问题
  • 认为条条大路通罗马: 但是每条路的路程差别非常大
  • 缺乏科学思考的习惯: 如何做到特殊到一般化，如果用一些特殊场景快速检验想法出现的错误
  • 喜欢钻牛角尖: 很多时候只能带来负面的收益

以上面的 Leetcode 问题为例，如何建立正确的思考方式

  1. 看样例: 从特殊到一般化，快速读懂题目的含义
  2. 举问题:
    1. 如何快速判断子串是否在循环串 $s$ 中
    2. 如何快速判断子串 $t$ 本质不同
    3. 如何计算字符串 $p$ 的所有子串中，包含于 $s$ 并且本质不同的串的个数
  3. 回答问题:
    1. $(t[i - 1] + 1) \% 26 = t[i]$
    2. 由于 $t$ 的 首字母 和 长度 唯一确定 $t$，用这两个参数就可以确定本质不同
    3. 根据 1 和 2，只需确定每个 首字母 对应的 最大长度，对于每个 首字母，有 最大长度 个子串。把不同的 首字母 加起来即可。

总结

感觉无论是做题还是平时生活中遇到困难，有很多困难和挑战都有很简单的解决方式，要善于观察问题的性质，不能钻牛角尖，千万别把问题想得过于复杂，那么可能很多困难，并没有我们想象得那么艰巨和困难。