比较字符串时的字符串方法与数组方法（大 O）

Question

假设我们正在比较两个字符串，这两个字符串具有导致异常发生的特殊字符 — 在这种情况下，# 字符会删除前一个字符。

这是一种构建字符串然后比较它们的解决方案，使用字符串方法 slice 和 concat:

const checkSame = (a, b) => {
  let one = ''
  for(let i = 0; i < a.length; i++){
    if(a[i] === '#'){
      one.slice(0, -1)
    } else {
      one.concat(a[i]);
    }
  }
  let two = ''
  for(let i = 0; i < b.length; i++){
    if(b[i] === '#'){
      one.slice(0, -1)
    } else {
      one.concat(b[i]);
    }
  }
  return one === two
};

这是另一个使用数组及其方法 push 和 pop 的解决方案：

export const compareTwoStrings2 = (a, b) => {
  let one = [];
  for (let i = 0; i < a.length; i++) {
    if (a[i] === "#") {
      one.pop();
    } else {
      one.push(a[i]);
    }
  }
  let two = [];
  for (let i = 0; i < b.length; i++) {
    if (b[i] === "#") {
      two.pop();
    } else {
      two.push(b[i]);
    }
  }
  for(let i = 0; i < one.length; i++){
      if(one[i] !== two[i]) return false;
  }
  return true;
};

第二个解决方案使用了一个额外的循环，这让我觉得如果给定一个 n 字符的字符串，它将花费 O(3n) 时间（最坏的情况），而第一个只需要 O(2n)时间.

这是正确的吗？连接和分割字符串是否比使用数组更有效？或者随着字符串长度的增加，两个字符串的最终比较是否也需要 n 时间？

Answer 1

O(3n) ~ O(2n) ~ O(n) 所以这两者的最坏情况复杂度基本上是一样的

参考：Big O notation > Multiplication by a constant

比较字符串时的字符串方法与数组方法（大 O）

String methods vs. Array methods when comparing strings (Big O)

javascript

arrays

string

performance

big-o