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;
};

参考资料