判断子序列

发表于 | 分类于 |
字数统计: 597 字 | 阅读时长 ≈ 2 分钟

题目描述：定字符串 s 和 t ，判断 s 是否为 t 的子序列。

你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长（长度 ~= 500,000），而 s 是个短字符串（长度 <=100）。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

示例 1:
s = “abc”, t = “ahbgdc” 返回 true.

示例 2:
s = “axc”, t = “ahbgdc” 返回 false.

1
2
3
4
5
class Solution {
    public boolean isSubsequence(String s, String t) {

    }
}

方法一：双指针（贪心算法）

本题询问的是，s 是否是 t 的子序列，因此只要能找到任意一种 s 在 t 中出现的方式，即可认为 s 是 t 的子序列。而当我们从前往后匹配，可以发现每次贪心地匹配靠前的字符是最优决策。

假定当前需要匹配字符 c，而字符 c 在 t 中的位置 x1 和 x2 出现(x1 < x2 )，那么贪心取 x1 是最优解，因为 x2  后面能取到的字符，x1也都能取到，并且通过 x1与 x2 之间的可选字符，更有希望能匹配成功。

这样，我们初始化两个指针 i 和 j，分别指向 s 和 t 的初始位置。每次贪心地匹配，匹配成功则 i 和 j 同时右移，匹配 s 的下一个位置，匹配失败则 j 右移，i 不变，尝试用 t 的下一个字符匹配 s。

最终如果 i 移动到 s 的末尾，就说明 s 是 t 的子序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
  public boolean isSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    int i = 0, j = 0;
    while(m > i && n > j) {
      if(s.charAt(i) == t.charAt(j)) {
        i++;
      }
      j++;
    }
    return m == i;
  }
}

复杂度分析：

  • 时间复杂度：O(m + n)，其中 m 为 s 的长度，n 为 t 的长度。每次无论是匹配成功还是失败，都有至少一个指针发生右移，两指针能够位移的总距离为 m + n

  • 空间复杂度：O(1)

执行结果：通过

  • 执行用时：1 ms, 在所有 Java 提交中击败了78.22%的用户

  • 内存消耗：37.4 MB, 在所有 Java 提交中击败了72.66%的用户