javascript - 使用字符串数组制作最长可能的词链

我正在尝试制作一个程序，将一组单词排序为最长可能的“链”(每个单词都以前一个单词结尾的字母开头)。一个示例链是 Uta h --> H awai i --> I dah o --> Ojit_strong Ojit_strong O

我一直在尝试解决这个问题大约 2 个小时。我一直使用的方法是蛮力，尝试生成所有可能的链，然后找到最长的链。我遇到的问题是我不知道如何在查找链时不陷入循环。
我尝试搜索是否已经在 StackOverflow 上回答了这个问题，我确实找到了有关此问题的已回答问题，但它是在 Python 中，当我测试已接受的解决方案时，它在大型列表中失败了。

这是一般的想法:

  var words = ["Alabama","Alaska","Arizona","Arkansas","California","Colorado","Connecticut","Delaware","Florida","Georgia","Hawaii","Idaho","Illinois","Indiana","Iowa","Kansas","Kentucky","Louisiana","Maine","Maryland","Massachusetts","Michigan","Minnesota","Mississippi","Missouri","Montana","New Hampshire","New Jersey","New Mexico","New York","North Carolina","North Dakota","Ohio","Oklahoma","Oregon","Pennsylvania","Rhode Island","South Carolina","South Dakota","Tennessee","Texas","Utah","Vermont","Virginia","Washington","West Virginia","Wisconsin","Wyoming"];

function longestChain(wordArray) {
  var allChains = [];
  for(var x = 0; x < words.length; x++) {
    /* I'm completely lost here
       store all chains generated with this start in the allChains array
       each chain should be an array
       example: ["Utah","Hawaii","Idaho","Oregon","New York","Kentucky"]
    */
  }
  var max = [0,0];
  for(var x = 0; x < allChains.length; x++) {
    if(allChains[x].length > max[0]) {
      max[0] = allChains[x].length;
      max[1] = x;
    }
  }
  return allChains[max[1]];
}

所以基本上我需要一种方法来找到所有可能的链而不循环。

最佳答案

下面的递归函数 getChains() 将为您的用例构建所有可能的链，并将它们存储在 allChains 变量中。

正如我在评论中提到的，这个问题感觉像是 Longest Path Problem 。如果是这种情况，您不能比蛮力解决方案做得更好。因此，如果单词数组变大，以下解决方案将变得非常慢，但对于给定的单词，它会在几秒钟内运行。

var words = ["Alabama","Alaska","Arizona","Arkansas","California","Colorado","Connecticut","Delaware","Florida","Georgia","Hawaii","Idaho","Illinois","Indiana","Iowa","Kansas","Kentucky","Louisiana","Maine","Maryland","Massachusetts","Michigan","Minnesota","Mississippi","Missouri","Montana","New Hampshire","New Jersey","New Mexico","New York","North Carolina","North Dakota","Ohio","Oklahoma","Oregon","Pennsylvania","Rhode Island","South Carolina","South Dakota","Tennessee","Texas","Utah","Vermont","Virginia","Washington","West Virginia","Wisconsin","Wyoming"];

var allChains = [];
var usedWords = [];
var currentChain = [];

getChains(currentChain, words, usedWords, allChains)

for(var i = 0; i < allChains.length; i++){
  document.write(allChains[i])
  document.write("<br>")
}

function getChains(currentChain, words, usedWords, allChains){
  var found = false;
  for(var x = 0; x < words.length; x++){
    if((currentChain.length == 0 || currentChain[currentChain.length-1].slice(-1) == words[x].toLowerCase().charAt(0)) && !usedWords.includes(x)){
      currentChain.push(words[x]);
      found = true;
      usedWords.push(x);
      getChains(currentChain, words, usedWords, allChains);
    }
  }
  if(!found){
      allChains.push(currentChain.slice());
  }
  currentChain.pop();
  usedWords.pop();
}

关于javascript - 使用字符串数组制作最长可能的词链，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57284406/