392. Is Subsequence
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
.
Follow up:
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.
Approach #1:
class Solution { public: bool isSubsequence(string s, string t) { int len1 = s.length(); int len2 = t.length(); if (len1 == 0) return true; queue<char> q; for (int i = 0; i < len1; ++i) { q.push(s[i]); } for (int i = 0; i < len2; ++i) { if (q.front() == t[i]) { q.pop(); } if (q.empty()) return true; } return false; } };
相关文章
- Facebook is Hiring!
- Is there a way to detect if a browser window is not currently active?
- What Is Token-Based Authentication and Who Uses It?
- the field is sometimes used inside synchronized block and sometimes used without synchronization
- 1135 Is It A Red-Black Tree (30 分)【难度: 难 / 知识点: 红黑树 未完成】
- MySQL创建表出现 Specified key was too long; max key length is 767 bytes
- linux内核中IS_ALIGNED是如何定义的?
- could not execute statement; SQL [n/a]; nested exception is org.hibernate.exception.DataException:
- Required request body is missing 错误解决
- vt-is-UTF8 - check whether current VT is in UTF8- or byte-mode. 检查当前VT是否处于VTF8模式或是字节模式.
- QThread 爬坑之旅(三种办法解决QObject: Cannot create children for a parent that is in a different thread)
- vue Inline JavaScript is not enabled. Is it set in your options?
- 华为游戏登录校验异常:javax.net.ssl.SSLHandshakeException: server certificate change is restrictedduring renego
- hdu 1325 Is It A Tree? (树、node = edge + 1、入度 <= 1、空树)
- 安装CocoaPods报错 - [!] The dependency `AFNetworking (~> 3.1.0)` is not used in any concrete target.
- HttpMessageNotReadableException: Required request body is missing: