Question

392. Is Subsequence

中文文档

Description

Given two strings s and t, return true_ if _s_ is a subsequence of _t_, or _false_ otherwise_.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

 

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

 

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 104
• s and t consist only of lowercase English letters.

 

Follow up: Suppose there are lots of incoming s, say s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>k</sub> where k &gt;= 10<sup>9</sup>, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Solutions

Solution 1: Two Pointers

We define two pointers $i$ and $j$ to point to the initial position of the string $s$ and $t$ respectively. Each time we compare the two characters pointed to by the two pointers, if they are the same, both pointers move right at the same time; if they are not the same, only $j$ moves right. When the pointer $i$ moves to the end of the string $s$, it means that $s$ is the subsequence of $t$.

The time complexity is $O(m + n)$, where $m$ and $n$ are the lengths of the strings $s$ and $t$ respectively. The space complexity is $O(1)$.

class Solution:
  def isSubsequence(self, s: str, t: str) -> bool:
    i = j = 0
    while i < len(s) and j < len(t):
      if s[i] == t[j]:
        i += 1
      j += 1
    return i == len(s)

class Solution {
  public boolean isSubsequence(String s, String t) {
    int m = s.length(), n = t.length();
    int i = 0, j = 0;
    while (i < m && j < n) {
      if (s.charAt(i) == t.charAt(j)) {
        ++i;
      }
      ++j;
    }
    return i == m;
  }
}

class Solution {
public:
  bool isSubsequence(string s, string t) {
    int m = s.size(), n = t.size();
    int i = 0, j = 0;
    for (; i < m && j < n; ++j) {
      if (s[i] == t[j]) {
        ++i;
      }
    }
    return i == m;
  }
};

func isSubsequence(s string, t string) bool {
  i, j, m, n := 0, 0, len(s), len(t)
  for i < m && j < n {
    if s[i] == t[j] {
      i++
    }
    j++
  }
  return i == m
}

function isSubsequence(s: string, t: string): boolean {
  const m = s.length;
  const n = t.length;
  let i = 0;
  for (let j = 0; i < m && j < n; ++j) {
    if (s[i] === t[j]) {
      ++i;
    }
  }
  return i === m;
}

impl Solution {
  pub fn is_subsequence(s: String, t: String) -> bool {
    let (s, t) = (s.as_bytes(), t.as_bytes());
    let n = t.len();
    let mut i = 0;
    for &c in s.iter() {
      while i < n && t[i] != c {
        i += 1;
      }
      if i == n {
        return false;
      }
      i += 1;
    }
    true
  }
}

public class Solution {
  public bool IsSubsequence(string s, string t) {
    int m = s.Length, n = t.Length;
    int i = 0, j = 0;
    for (; i < m && j < n; ++j) {
      if (s[i] == t[j]) {
        ++i;
      }
    }
    return i == m;
  }
}

bool isSubsequence(char* s, char* t) {
  int m = strlen(s);
  int n = strlen(t);
  int i = 0;
  for (int j = 0; i < m && j < n; ++j) {
    if (s[i] == t[j]) {
      ++i;
    }
  }
  return i == m;
}