【LeetCode】 392. Is Subsequence

Description

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

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).

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.

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• Both strings consists only of lowercase characters.

給予一個字串s和一個字串t，檢查s是否為t的子序列。

一個字串的子序列是指一個新字串，它透過刪除原字串中的部分字元(可以不刪除)且不移動其餘字元的相對位置所得到(例如，"ace"是"abcde"的子序列而"aec"不是)。

進階：
如果有一堆輸入 S，分別為 S1, S2, … , Sk 且 k >= 1B，你想要一個個檢查T是否為它的子序列。在這樣的情況下，你要怎麼更改你的程式碼？

工作人員：
特別感謝@pbrother加入這個問題和提供全部的測試資料。

限制：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 兩個字元都只包含小寫字元。

Example:

Example 1:

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


Example 2:

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

Solution

• 用一個箭頭(int)指向較短字串s的開頭，然後用迴圈跑一次較長的字串t。
  • 當兩者相同時，將s的箭頭往下移一個字。
• 當t跑完之後，檢查s的箭頭是否指到尾端的後一格。

Code

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

tags: LeetCode C++