Google Kickstart 2022 Round A的题解如何详细解析？

本文共计2863个文字，预计阅读时间需要12分钟。

Speed Typing 题意概述：给出两个字符串 I 和 P，询问能否通过删除 P 中的一些字符得到 I。

示例：给出字符串 I 和 P，例如 I=I 和 P=P，询问是否可以通过删除 P 中的字符得到 I。如果能，需要删除字符的个数是多少？

数据模型：[1≤|I|,|P|≤10^5]，双指针设置：设置两个指针 i 和 j 分别指向 I 和 P。

Speed Typing 题意概述

给出两个字符串I和P，问能否通过删除P中若干个字符得到I？如果能的话，需要删除字符的个数是多少？

数据规模

\[1≤|I|,|P|≤10^5 \]

双指针

设置两个指针i和j分别指向I和P的第一个字符，滑动指针j，如果j指向的字符与i指向的字符相同，则让i向后滑动一个字符，当i滑动到I字符串末尾或j滑动到P字符串末尾后即可结束循环。如果i滑动到I字符串末尾，则说明可以通过删除P中若干个字符得到I，那么删除的字符个数为\(|P|-|I|\)；反之则不能。

复杂度

• 时间复杂度为\(O(max(|I|,|P|))\)。