JS实现isSubsequence子序列判断 本地正常Udemy判题报错排查

我正在学习JavaScript，近期在练习DSA相关题目，当前尝试解决isSubsequence函数编写问题。

题目要求 #

编写函数isSubsequence，接收两个字符串作为入参，校验第一个字符串的字符是否构成第二个字符串的子序列，即第一个字符串的所有字符需要在不改变原有顺序的前提下，在第二个字符串中存在对应匹配。

参考测试用例：

• isSubsequence('hello','hello world') // true
• isSubsequence('sing','sting') // true
• isSubsequence('abc','abracadabra') // true
• isSubsequence('abc', 'acb') // false

个人实现代码 #

const isSubsequence = (str1, str2) => {
  const createCharObj = (string) => {
    let outputObj = {};
    for (let i = 0; i < string.length; i++) {
      if (outputObj[string[i]]) {
        outputObj[string[i]]++;
      } else {
        outputObj[string[i]] = 1;
      }
    }
    return outputObj;
  };
  let charObj1 = createCharObj(str1);
  let charObj2 = createCharObj(str2);
  let compare = "";

  for (let key in charObj2) {
    if (charObj2[key] < charObj1[key]) {
      return false;
    } else {
      let exceed = charObj1[key];
      let i = 0;
      while (i < exceed) {
        compare += key;
        i++;
      }
    }
  }
  return compare === str1;
};

console.log(isSubsequence("hello", "hello world"));
console.log(isSubsequence("sing", "sting"));
console.log(isSubsequence("abc", "abracadabra"));
console.log(isSubsequence("abc", "acb"));

遇到的问题 #

我知道当前实现时间效率不高，但自认为逻辑合理。同一份代码在Udemy平台IDE中运行判题时返回expected false to be true报错，在本地VS Code中运行给定的4个测试用例却无异常，希望定位代码中存在的错误。

你的代码逻辑本身存在硬伤，报错和本地测试用例覆盖不全、JS对象遍历顺序的特殊规则直接相关：

1. 核心逻辑不符合子序列校验要求
   子序列校验的核心是字符出现的先后顺序匹配，但你的实现本质上只是统计两个字符串的字符频次，再按对象键的遍历顺序拼接字符串和原str1做对比，完全没有追踪字符在str2中的实际出现顺序，从根上就不满足题目的顺序要求。
2. JS对象键遍历顺序不可靠是触发报错的直接原因
   ES6规范中for...in遍历对象键的顺序不是严格按键插入的先后顺序：整数类型的字符串键（比如'1'、'2'）会被优先按数值升序遍历，之后才会按插入顺序遍历其他字符串键。
   比如Udemy测试用例中如果存在isSubsequence('a1b', 'a1b')这类包含数字字符的场景：

• 你创建的charObj2插入键的顺序是'a' -> '1' -> 'b'
• 但for...in遍历时会先遍历数字键'1'，再遍历'a'、'b'
• 最终拼接出来的compare值是'1ab'，和str1'a1b'不相等，代码错误返回false，但实际正确结果应该是true，就会触发expected false to be true的报错。
  你本地测试的4个用例全是纯字母字符串，没有触发对象键的特殊排序规则，所以看起来运行正常。

3. 存在隐藏逻辑漏洞
   如果str1中存在str2没有的字符，你遍历的是charObj2的键，根本不会检查到str1独有的字符：比如isSubsequence('axc', 'abc')，str1中的x在charObj2中不存在，你的代码不会进入对应判断分支，最后拼接的compare是'ac'，虽然结果返回false，但判断逻辑完全是巧合，没有做显式校验。

子序列问题最优解法是双指针法，时间复杂度O(n+m)，空间复杂度O(1)，完全规避顺序不可靠的问题：

const isSubsequence = (str1, str2) => {
  // 边界处理：str1为空串时默认是子序列
  if (str1.length === 0) return true;
  let p1 = 0; // 指向str1当前待匹配的字符
  for (let p2 = 0; p2 < str2.length; p2++) {
    // 字符匹配则移动str1的指针
    if (str2[p2] === str1[p1]) {
      p1++;
      // str1所有字符都匹配完成，直接返回true
      if (p1 === str1.length) return true;
    }
  }
  // 遍历完str2还没匹配完str1，返回false
  return false;
}

内容的提问来源于stack exchange，提问作者Akash