问答

当前位置

Google 面试题 | 检查子序列

  • Ta: 高助教

题目描述

给我们两个字符串,问我们第一个字符串是否是第二个字符串的子序列。

样例

Example 1:
s = "abc", t = "ahbgdc"
Return true.

Example 2:
s = "axc", t = "ahbgdc"
Return false.

解题思路

这道题目需要判断第一个是否为第二个字符串的子序列。

这里我们可以用到双指针移动的方法。以 i 作为第一个字符串 s 的指针,j 为第二个字符串 t 的指针。

一开始 i 和 j 都指向字符串的开头,然后每一次我们都将j往后移动一个单位,然后判断 s[i] 是否和 t[j] 相等,如果相等我们就将 i 往后移动一个单位。

这样如果最后 i 能移动到 s 的最后一位,那么说明 s 是 t 的子序列,否则不是,因为我们每一步都在检查是否有重复都子序列,指针 j 会检查 t 里面所有可能出现在 s 里面的子序列。总共复杂度为 O(s.length + t.length)。

参考程序

1. Java 版本

2. c++ 版本

3. python 版本

面试官角度分析

这道题就是简单的两个指针问题考察,能够快速想到双指针并且能够正确估算出时间复杂度,那么此题就可以得到 hire 的评价。

题目答案链接

Is Subsequence 参考代码

相关题目

Edit Distance
Distinct Subsequences

0 个回复

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1