392. Is Subsequence

Leetcode 問題: 392. Is Subsequence
Categories:
Tags:

題目

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

傳入兩個字串 s (要比對的字串) 跟 t (原始字串)，確認傳入的 字串 s 是不是 t (原始字串) 的子字串序列 (subsequence)

是 子字串序列 (subsequence) 的話，字母的出現順序要相同

字母 abc 是 ahbgdc 的 subsequence

原始字串 ahbgdc a h b g d c
比較字串 abc a b c

答案是 Yes，是子字串序列

字母 acb 不是 ahbgdc 的 subsequence

原始字串 ahbgdc a h b g d c
比較字串 acb a c

答案是 No，不是子字串序列

Example

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

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

演算法

  • 建立 「檢查的字母」指標及「原始的字母」指標，比較字母是否相符
  • 若找到了相同的字，將「檢查的字母」指標往後移動，繼續檢查下一個
  • 不管有沒有找到相同的字，「原始的字母」指標都要往後繼續找
    • 因為是 subsequence 的話，字母的出現順序要相同
    • 所以有用到的字不能繼續用，沒有用到的字也沒用
  • 若 「檢查的字母」指標全部檢查完，與檢查的字串長度相等，表示這個字串是 子字串序列 (subsequence)

答案

JavaScript

/**
 * @param {string} checkSubsequenceText
 * @param {string} originalText
 * @return {boolean}
 */
var isSubsequence = function(checkSubsequenceText, originalText) {
    if (checkSubsequenceText.length > originalText.length) {
        // 如果要檢查的字串比原始字串長，不用檢查，不可能是 subsequence
        return false;
    }

    // 「檢查的字母」指標
    let checkPointer = 0;
    // 「原始的字母」指標
    let originalPointer = 0;

    while (checkPointer < checkSubsequenceText.length && originalPointer < originalText.length) {
        // 當檢查字串指標都還沒檢查完，繼續檢查
        // 「檢查的字母」指標
        let checkLetter = checkSubsequenceText[checkPointer];
        // 「原始的字母」指標
        let originalLetter = originalText[originalPointer];

        if (checkLetter == originalLetter) {
            // 若找到了相同的字，將檢查字往後移動，繼續檢查下一個
            checkPointer++;
        }
        // 不管字有沒有找到，都要往後使用下一個字，有用到的字不能繼續用，沒有用到的字也沒用
        originalPointer++;
    }

    let isTextSubsequence = false;
    if (checkPointer == checkSubsequenceText.length) {
        // 如果完全比對，都把字找完了，表示是 subsequence
        isTextSubsequence = true;
    }

    return isTextSubsequence;
};

參考資料