JavaScript中在对象数组中匹配字符串前缀的最优解决方案

你需要实现的是：给定API返回的字符串result，在对象数组arrayCode中找到code为result前缀的对象，返回其索引；当数组数据量较大时，要给出最优实现方案。

你当前的基础实现是线性遍历数组，每次用indexOf判断code是否是result的前缀，这种方法的时间复杂度是O(n*m)——n是数组长度，m是code的平均长度。当数组规模达到十万甚至百万级时，这种线性遍历的效率会急剧下降，完全无法满足性能要求。

根据code的长度是否固定，我们有两种针对性的高效方案：

方案1：哈希表预处理（code长度固定时用） #

如果所有code的长度都一致（比如示例里都是4位），提前把code和对应的索引存到哈希表里，查询时直接截取result的前固定长度字符串，去哈希表中取索引就行。

代码示例：

// 一次性预处理，把code和索引映射好
const codeToIndex = new Map();
arrayCode.forEach((item, idx) => {
  codeToIndex.set(item.code, idx);
});

// 查询逻辑
const result = "485178485451478";
// 假设code都是4位，截取前4位
const prefix = result.slice(0, 4);
// 没找到就返回-1，可根据需求调整默认值
const targetIndex = codeToIndex.get(prefix) ?? -1;
console.log(targetIndex); // 输出3

这种方案预处理只需要O(n)时间，每次查询都是O(1)，非常适合需要频繁查询的场景。

方案2：前缀树（Trie）预处理（code长度不固定时用） #

如果code的长度不统一，前缀树是最优解。前缀树可以高效存储所有code的前缀结构，查询时只需要遍历result的字符，直到找到匹配的code，直接返回对应的索引。

实现代码 #

// 定义前缀树节点
class TrieNode {
  constructor() {
    this.children = new Map();
    this.index = -1; // 存储对应数组的索引，-1表示不是某个code的结尾
  }
}

// 构建前缀树
function buildTrie(arr) {
  const root = new TrieNode();
  arr.forEach((item, idx) => {
    let currentNode = root;
    for (const char of item.code) {
      if (!currentNode.children.has(char)) {
        currentNode.children.set(char, new TrieNode());
      }
      currentNode = currentNode.children.get(char);
    }
    // 标记当前code的结尾节点，存入索引
    currentNode.index = idx;
  });
  return root;
}

// 查询匹配的前缀索引
function findMatchIndex(trieRoot, resultStr) {
  let currentNode = trieRoot;
  for (const char of resultStr) {
    if (!currentNode.children.has(char)) {
      break;
    }
    currentNode = currentNode.children.get(char);
    // 找到匹配的code，直接返回索引
    if (currentNode.index !== -1) {
      return currentNode.index;
    }
  }
  // 没有找到匹配的前缀，返回-1
  return -1;
}

// 使用示例
const result = "485178485451478";
const arrayCode = [
  { "code": "2150" },
  { "code": "4857" },
  { "code": "5046" },
  { "code": "4851" },
  { "code": "4154" },
  { "code": "9654" },
  { "code": "1254" },
  { "code": "9562" },
  { "code": "1457" },
  { "code": "6479" }
];

const trie = buildTrie(arrayCode);
const targetIndex = findMatchIndex(trie, result);
console.log(targetIndex); // 输出3

这种方案的预处理时间是O(totalChars)（totalChars是所有code的字符总数），查询时间是O(k)（k是result的长度或者匹配到的code的长度），在code长度不固定、数组规模大的场景下，性能优势非常显著。

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