javascript - 使用字符串数组创建最长可能的单词链

Question

我正在尝试编写一个程序，将单词数组排序为最长的可能“链”(每个单词都以前一个单词结尾的字母开头)。一个示例链是 Utah --> Hawaii --> Idaho --> Oregon.

我已经尝试解决这个问题大约 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]];
}

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

Answer 1

首先，这是一个最长的寻路问题。

如果图是双向的，则解决方案是 NP 困难的。你必须解决它使用 递归或回溯。如果输入大小很小，您也可以使用 musking dp 解决它。有人已经分享了基于递归的解决方案。

如果图是有向但无环的，则它有解。您可以使用拓扑排序等算法来解决它。 Link

但是如果图是有向循环图，它的行为就像双向图。所以解决方案很难。

你的问题是一个有向循环图。
例如，
让 words={"abc","cde","efa"}
通过使用这些词，如果我们制作一个图，那么 word[0] 将连接到 word[1]，word[1] 将连接到 word[2]，word[2] 将连接到 word[0]。< br/> 所以它创建了一个循环图。