时间戳

首页 > 解决方案 > 给定任意数量的不同字母，我如何找到包含所有可能的两个字母序列的最短字符串？

string - 给定任意数量的不同字母，我如何找到包含所有可能的两个字母序列的最短字符串？

问题描述

我很难解释，因为英语是我的第二语言，而且我的逻辑很差。我会举一些例子来帮助你。

如果字母是 ABC，我正在寻找的有效组合是 AB、AC、BA、BC、CA、CB。简单地组合成一个字符串： ABACBABCCACB 但该字符串中仍有重复项。如果我“压缩”它，我会得到：ABACBCA

我不确定如何更好地解释，但我正在寻找一种能够产生“压缩”版本的算法。

标签： stringalgorithm

解决方案

要了解 jenesaisquoi 的评论，如果我们删除连续的重复项，则可以使用 de Brujin 序列。

JavaScript 中的示例（改编自Wikipedia上的 Python 代码）。请记住，de Brujin 序列是环绕的，因此我们需要包括适当的重叠来获得所有组合。

function de_bruijn(k, n){
  /***
  de Bruijn sequence for alphabet k
  and subsequences of length n.
  ***/
  var alphabet
  
  if (typeof k == 'number'){
    alphabet = new Array(k).fill(null)
      .map((_, i) => String(i))
    
  } else if (typeof k == 'string'){
    alphabet = k
    k = k.length
  }

  var a = new Array(k * n).fill(0)
  var sequence = []

  function db(t, p){
    if (t > n){
      if (n % p == 0)
        sequence = sequence.concat(
          a.slice(1, p + 1))
        
    } else{
      a[t] = a[t - p]
      db(t + 1, p)
      for (let j=a[t-p]+1; j<k; j++){
        a[t] = j
        db(t + 1, t)
      }
    }
  }
 db(1, 1)

  return sequence.map(i => alphabet[i])
    .join("")
}

// https://stackoverflow.com/questions/30716829/how-to-remove-repeated-entries-from-an-array-while-preserving-non-consecutive-du
function removeDuplicates(str){
  return str.split("").filter(function(item, pos, arr){
    return pos === 0 || item !== arr[pos-1]; }
  ).join("")
}

var result = de_bruijn(3, 2)
console.log(result)
console.log(removeDuplicates(result))

result = de_bruijn("abc", 2)
console.log(result)
console.log(removeDuplicates(result))

推荐阅读