0187. Repeated DNA Sequences ============================ 题目信息 -------- :题号: 0187. 重复的 DNA 序列 :难度: Medium :主题: 字符串、滑动窗口、位编码、三态去重 :原题: `LeetCode 0187 `_ :重点: 将固定四字符窗口编码为 20 位状态,并在第二次出现时恰好提交一次结果 题目重述 -------- 给定只包含 ``A、C、G、T`` 的 DNA 字符串 ``s``,找出所有出现至少两次、长度恰为 10 的连续片段。每种重复片段只返回一次,结果顺序任意。 若字符串长度小于 10,不存在合法窗口,返回空数组。 自建示例 -------- .. code-block:: text 输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT" 输出:["AAAAACCCCC", "CCCCCAAAAA"] .. code-block:: text 输入:s = "AAAAAAAAAAAAA" 输出:["AAAAAAAAAA"] 四个长度 10 的窗口内容相同;第二次出现时输出,第三、第四次不能重复追加。 .. code-block:: text 输入:s = "ACGTACGTA" 输出:[] 长度只有 9,没有完整窗口。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: std::vector hashStringWindows( const std::string& s) { std::unordered_map occurrences; std::vector repeated; for (int start = 0; start + 10 <= static_cast(s.size()); ++start) { std::string window = s.substr(start, 10); if (++occurrences[window] == 2) { repeated.push_back(window); } } return repeated; } unsigned int encode(char nucleotide) { switch (nucleotide) { case 'A': return 0U; case 'C': return 1U; case 'G': return 2U; default: return 3U; } } std::vector encodedWindows( const std::string& s) { if (s.size() < 10U) { return {}; } constexpr unsigned int state_count = 1U << 20U; constexpr unsigned int window_mask = state_count - 1U; std::vector state(state_count, 0U); std::vector repeated; unsigned int code = 0U; for (std::size_t index = 0; index < s.size(); ++index) { code = ((code << 2U) | encode(s[index])) & window_mask; if (index < 9U) { continue; } if (state[code] == 0U) { state[code] = 1U; } else if (state[code] == 1U) { repeated.push_back(s.substr(index - 9U, 10U)); state[code] = 2U; } } return repeated; } public: std::vector findRepeatedDnaSequences( std::string s) { return encodedWindows(s); } }; 题解 ---- 原始搜索重复扫描后缀 ~~~~~~~~~~~~~~~~~~~~ 字符串长度为 ``n`` 时共有 ``n-9`` 个候选窗口。最直接的方法是对每个窗口向后搜索相同 片段;许多后缀会被不同起点反复比较,最坏达到 ``O(n²)``。 ``hashStringWindows`` 保存每种十字符子串的出现次数。每个窗口只查询一次哈希表,并在计数 刚变成 2 时输出,因此期望时间降为 ``O(n)``。这个基线已经正确,但每前进一步都要构造 一个新子串,并对十个字符计算哈希;哈希表还保存字符串键。 题目给出了可进一步利用的固定结构:字符只有四种,窗口长度永远是 10。窗口无需以字符串 作为状态,可以无碰撞地装进一个整数。 四字符如何变成 20 位编码 ~~~~~~~~~~~~~~~~~~~~~~~~ 为每个字符分配两位: .. code-block:: text A -> 00 C -> 01 G -> 10 T -> 11 十个字符正好占 20 位,也可看成十位四进制数。固定长度保证表示唯一:即使开头的 ``A`` 编码为零,也不会与较短字符串混淆,因为状态表只在形成完整十字符窗口后查询。 处理新字符时执行: .. code-block:: text code = ((code << 2) | newValue) & ((1 << 20) - 1) 左移为新字符腾出最低两位,按位或写入其编码;20 位掩码删除已经滑出窗口的最高两位。 因此处理下标 ``index`` 后,``code`` 始终表示最近至多 10 个字符;当 ``index >= 9`` 时, 它恰好对应窗口 ``s[index-9..index]``。 滚动状态删除了哪些工作 ~~~~~~~~~~~~~~~~~~~~~~ 相邻十字符窗口共享九个字符。字符串基线每次重新复制和哈希这九个公共字符;滚动编码只做 一次左移、写入和掩码,就从旧窗口状态得到新窗口状态。总共只有 ``2^20`` 种编码,可以 直接用数组索引,不存在哈希冲突,也不需要存字符串键。 只有在某片段确定需要返回时,代码才调用 ``substr`` 复制一份十字符结果。中间所有窗口都 保持整数形式。 为什么需要三种出现状态 ~~~~~~~~~~~~~~~~~~~~~~ 仅记录“见过/没见过”的布尔值,可以识别第二次出现,却无法区分“刚刚重复、应该输出”和 “以前已经输出、不能再次加入”。``state[code]`` 使用三种值: * ``0``:此前没有完整窗口使用该编码; * ``1``:此前出现一次,尚未输出; * ``2``:此前至少出现两次,结果中已经有一个副本。 当前窗口到来时,``0 -> 1`` 不输出;``1 -> 2`` 并输出;状态 2 不再变化。于是输出动作 与“第二次出现”这一唯一状态转移绑定,不需要第二个结果集合做去重。 具体状态走读 ~~~~~~~~~~~~ ``"AAAAAAAAAAAAA"`` 产生四个相同编码 0: .. code-block:: text 窗口序号 到来前状态 动作 到来后状态 1 0 只记录首次出现 1 2 1 输出 AAAAAAAAAA 2 3 2 已输出,跳过 2 4 2 已输出,跳过 2 如果只有九个字符,循环虽会逐字符更新部分编码,但 ``index < 9`` 时不会访问状态表; 函数还提前返回空结果,完整避免不存在的窗口。 代码对应关系与正确性 ~~~~~~~~~~~~~~~~~~~~ ``encode`` 把题目保证合法的四种字符映射到 ``0..3``,``default`` 因而只代表 ``T``。 掩码不变量保证每个候选窗口都恰好查询一次;定长四进制表示保证相同编码当且仅当十字符 片段相同;三态转移保证每个至少出现两次的编码在第二次命中时输出一次,之后不再输出。 所以结果没有假重复、没有遗漏,也没有多份副本。 方案选择与复杂度 ~~~~~~~~~~~~~~~~ 字符串哈希基线期望时间 ``O(n)``,保存至多 ``O(n)`` 个字符串键,并为窗口创建短子串; 位编码主解严格线性扫描,时间 ``O(n)``。状态表固定为 ``2^20`` 个字节,约 1 MiB;相对 本题固定窗口和字符域可记为 ``O(1)``,结果字符串空间另计。位方案利用固定结构删除了窗口 复制、字符串哈希和碰撞处理,因此 ``encodedWindows`` 作为主解。