在给定序列长度的字符串数组中找到最常见的子字符串

Question

祝你一切顺利！

我遇到了一个有趣的序列问题，我一直在努力解决它：“在具有特定字符数的字符串数组中找到最常见的序列。”

输入：(["abc", "usbc", "bcde"], 2) 输出："bc"

输入：(["terrific, specific"], 4) 输出："ific"

这是我目前的情况：

function commonSubstring(array, length) {
  let popular = '';
  let seq = []
  let map = {}

  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array[i].length; j++) {
      const str = array[i].slice(j, j+length)
      if (str.length === length && array[i].includes(str)) {
        seq.push(str)
      }
      if (array[i].includes(seq[j]) && !map[seq[j]]) {
        map[seq[j]] = 1
        // console.log(seq[j])
      } else {
        map[seq[j]]++
        j++
      }
    }
  }
  console.log(map)
  return popular
}

我试图做的是遍历每个字符串元素并找到公共序列，然后我添加了一个地图以建立一个点系统，然后最终找到点数最多的键和 return 那个键.

老实说，我有点迷茫。我如何有效地解决这个问题？

谢谢！

Answer 1

这是一个使用 for 循环和递归调用的解决方案

const getSequence = (list, length, check) => {
  if(!list.length || (check && check.length < length)) {
   return false;
  }
  let result = check || list[0];  //setting first item as a result
  let found = true;

  let i;
  for(i = 1; i<list.length; i++) {
    if(list[i].indexOf(result.substring(0, length)) == -1) {
      found = false;
      break;
    }
  }
  if(!found) {
     let val = getSequence(list, length, result.substring(1, result.length)) //calling same function by removing first char 
     if(val) {
      return val;
     }
  }
  else {
    return result.substring(0, length);
  }
}


console.log(getSequence(["abc", "usbcj", "bcdeh"], 2))
console.log(getSequence(["terrific", "specific"], 4))
console.log(getSequence(["test", "text"], 2))

Answer 2

这是对您的代码的修改，它实现了我上面评论中的建议：

缩短内部 (j) 循环以仅循环遍历可容纳当前字符串长度的偏移量，
删除长度检查，因为不再需要它们，
删除数组中不需要的子字符串的检查。

我还添加了最大搜索，这样它就会 return 答案：

function commonSubstring(array, length) {
  let popular = '';
  let seq = []
  let map = {}

  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array[i].length - length + 1; j++) {
      const str = array[i].slice(j, j+length)
      if (!map[str]) {
        map[str] = 1
      } else {
        map[str]++
      }
    }
  }
  // console.log(map)
  
  let maxv = 0;
  for(let prop in map) {
    if(map[prop] > maxv) {
      popular = prop;
      maxv = map[prop];
    }   
  }
  return popular
}

console.log(commonSubstring(["abc", "usbcj", "bcdeh"], 2))
console.log(commonSubstring(["terrific", "specific"], 4))
console.log(commonSubstring(["test", "text"], 2))

这在 O(n*m) 中运行，其中 n 是输入字符的总数，m 是长度参数。据我所知，这是解决此问题的最佳 CPU 复杂度。至于执行效率，这应该已经很接近最佳了。

在给定序列长度的字符串数组中找到最常见的子字符串

Find the most common substring in an array of strings with a given sequence length

javascript

arrays

string

sequence