欣迪

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

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 s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isSubsequence = function(s, t) {
    let current = -1
    for (let i = 0; i < s.length; i++) {
        const idx = t.indexOf(s[i], current + 1)
        if (idx > current) {
            current = idx
        } else {
            return false
        }
    }
    return true
};

思路

簡單來說,通過找 s 中的字符是否在 t 中出現,並且出現的順序和 s 是否相同,來判斷 s 是否為 t 的子序列。

indexOf 的第二個變數常被忽略:

str.indexOf(searchValue[, fromIndex])

其中,str 表示要查找的字串,searchValue 表示要查找的字符或子串,fromIndex 表示查找的起始位置(選擇性)。

let str = "Hello World!";

console.log(str.indexOf("o")); // 輸出 4
console.log(str.indexOf("l", 3)); // 輸出 2
console.log(str.indexOf("x")); // 輸出 -1

訂閱 IT-Monk

訂閱最新文章的發布消息! 😚😚😚
Loading

作者介紹 - 欣迪

欣迪

從設計到寫程式,發現自己有追求前端技巧的自虐傾向。不斷的踩坑,再從坑裡爬出來,慢慢對攀岩有點心得。 目前在多間公司擔任網站設計顧問。 同時也是網站架設公司負責人。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *