day-12-字符串isMatch

[H246802]

请用 JavaScript 实现一个方法，该方法能够判断两个字符串是否 匹配，如：

function isMatch(str1, str2){
  // your code
}
isMatch('something', 'gnihtemos') // true
isMatch('aaa', 'aa') // false
isMatch('abb', 'baa') // false
isMatch('hello', 'olelh') // true

使用上一章节的 execTimes 方法测试你的方案执行10000次的时长，该方案是否是最优方案？如果不是，请给出最优方法，并说明时间复杂度

[H246802]

此处匹配的定义应该是，判断两个字符串包含内单个字符是否满足一一对应关系

function isMatch(a, b) {
    if (typeof a !== "string" || typeof b !== "string") {
        console.error('请输入两个字符串')
        return
    }
    if (a.length !== b.length) {
        return false
    }
    // 字符串先拆成数组,再对数组排序,之后判断二者对比是否一致
    return a.split("").sort().join("") === b.split("").sort().join("") 
}

[H246802]

回到上回问题代码 进行测试

function execTimes(call,times) {
  // your code
  return function(){
    console.time()
    let begin = Date.now()
    for(let i = 0 ; i < times ; i++){
          // 与之前不一致,进行修改部分代码
	  // call(arguments[0] ? arguments[0] : '')
          call(...arguments)
    }
    let end = Date.now()
    console.log('执行' + times + '次，耗时' + (end - begin) + 'ms')
    console.timeEnd()
  }
}

按照前文,进行测试,我们可以知道排序耗时主要取决于 isMatch 函数
isMatch 函数中split,join 各有一次遍历, 而字符集数组的 sort 方法
在v8引擎内
Google Chrome 对 sort 做了特殊处理，对于长度 <= 10 的数组使用的是插入排序(稳定排序算法) ，
10 的数组使用的是快速排序。快速排序是不稳定的排序算法。

In-place QuickSort algorithm.
For short (length <= 10) arrays, insertion sort is used for efficiency.

归并排序,快速排序的平均时间复杂度是 O(nlogn) 如果想要再进行优化,我们需要将时间复杂度降低到O(n)

[H246802]

根据题意,进行优化,做好的办法是不使用排序算法,使用其他方法判断

优化后代码如下

function isMatch(a, b) {
  if (typeof a !== "string" || typeof b !== "string") {
    console.error('请输入两个字符串')
    return
  }
  if (a.length !== b.length) {
    return false
  }
  const hash = {}
  // 先记录第一个字符串包含的各个元素信息
  for (let i = 0; i < a.length; ++i) {
    const key = a[i]
    if (hash[key]) {
      hash[key] += 1
    } else {
      hash[key] = 1
    }
  }
  for (let j = 0; j < b.length; ++j) {
    const key = b[j]
    if (!hash[key]) {
      return false
    } else {
      hash[key] -= 1
    }
  }
  return true
}

[H246802]

前者时间记录

---

后者时间记录