# LeetCode 392. Is Subsequence

## Description

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

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

Example 1:
s = “abc”, t = “ahbgdc”

Return true.

Example 2:
s = “axc”, t = “ahbgdc”

Return false.

If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

## 描述

s = “abc”, t = “ahbgdc”

s = “axc”, t = “ahbgdc”

### 思路

• 依次检查 s 中的每个字符是否出现在 t 中，并且要求 s 中后面的字符的在 t 中出现的位置对应递增。
• 当有很多个 s ，只有一 t 个时，可以考虑用字典对 t 建立索引。键为 t 中的字符，值为 t 对应字符出现过的所有索引（递增）。
• 查询 s 中的字符时，使用二分搜索，要求 s 中后一个字符的在 t 中的索引大于前一个字符的索引。
```# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-08-17 13:53:03

import bisect
from collections import defaultdict

class Solution:
def __init__(self):
self.__isinit = False
self.__dict = defaultdict(list)

def __build(self, t):
for index, char in enumerate(t):
self.__dict[char].append(index)
self.__isinit = True

def isSubsequence(self, s: str, t: str) -> bool:
if not self.__isinit:
self.__build(t)

next_ = -1
for char in s:
next_ = self.__check(char, next_)
if next_ == -1:
return False

return True

def __check(self, char, index):
if char not in self.__dict:
return -1
next_ = bisect.bisect_right(self.__dict[char], index)
return self.__dict[char][next_] if next_ < len(self.__dict[char]) else -1
```