使用字符串数组构造最长的单词链

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]];
}

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

- Joseph Mahma

---

尝试获取一个包含所有单词的“首字母”的数组作为第一个数组，然后获取所有单词的“末尾字符”作为第二个数组。然后按出现次数对它们进行排序，然后将最不频繁的连接在一起，直到用完为止。 - user11809641

频繁的贪心算法可能会走入死路，而且离最优解相差甚远。很容易陷入死局。 - claasic

这感觉像是一种最长路径问题，因此枚举所有可能的链确实是一个不错的开始。 - SaiBot

@SaiBot 这绝对是最长路径问题。对于无向图，这是NP难题。但这是一个有向图：每个单词都是一个顶点，如果A的最后一个字母是B的第一个字母，则存在从顶点A到B的边缘。对于DAG，它可以在多项式时间内解决，但是该图可能具有循环，并且我不太记得如何在循环有向图中找到最长路径。 - slider

可能是将数字成对排列，使相邻的成对成员相等的重复问题。 - גלעד ברקן

Answer 1

首先，这是一个最长路径查找问题。

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

如果图是定向无环图，则有解。您可以使用类似拓扑排序的算法来解决。链接 但是，如果图是定向循环图，则行为类似于双向图。因此，解决方案是np困难的。

您的问题是一个定向循环图。 例如， 让words={"abc","cde","efa"} 通过使用这些单词制作图表，word [0]将连接到word [1]，word [1]将连接到word [2]，而word [2]将连接到word [0]。 因此创建了一个循环图。

- mahbubcseju

Answer 2

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

正如我在评论中提到的，这个问题感觉像是最长路径问题。如果是这种情况，你不能比暴力解决方案更好。因此，如果单词数组增长，以下解决方案将变得非常慢，但对于给定的单词，它可以在几秒钟内运行。

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();
}

- SaiBot

Answer 3

你可以将以相同字母开头和结尾的单词分开，并使用其余部分构建一棵树。然后获取最长的单词数组，并尝试添加以相同字母开头/结尾的单词。

function getLongestWords(words) {
    function getTree(word, seen) {
        var last = word.slice(-1).toUpperCase();
        if (!data[last]) return {};
        return data[last].reduce(getChildren(seen.concat(word)), {});
    }

    function getChildren(seen) {
        return function (r, w) {
            if (!seen.includes(w)) r[w] = getTree(w, seen);
            return r;
        };
    }

    function getLength(array) {
        return array.reduce((l, { length }) => l + length, 0);
    }

    function getLongest(object, result = [], parts = []) {
        var keys = Object.keys(object);
        if (!keys.length) {
            if (getLength(parts) > getLength(result[0] || [])) {
                result.length = 0;
                result.push(parts);
            } else if (getLength(parts) === getLength(result[0])) {
                result.push(parts);
            }
            return result;
        }
        keys.forEach(k => getLongest(object[k], result, parts.concat(k)));
        return result;
    }

    var notSame = [],
        same = {},
        data = words.reduce((r, w) => {
            var key = w[0],
                last = w.slice(-1);
            if (key === last.toUpperCase()) {
                same[key] = same[key] || { words: [], used: [] };
                same[key].words.push(w);
            } else {
                r[key] = r[key] || [];
                r[key].push(w);
                notSame.push(w);
            }
            return r;
        }, {}),
        tree = notSame.reduce(getChildren([]), {});

    return getLongest(tree).map((a, i) => {
        var key = a[0][0];
        if (key in same && !same[key].used.includes(i)) {
            same[key].used.push(i);
            return same[key].words.concat(a);
        }
        return a.reduce((r, w) => {
            key = w.slice(-1).toUpperCase();
            r.push(w);
            if (key in same && !same[key].used.includes(i)) {
                same[key].used.push(i);
                r.push(...same[key].words);
            }
            return r;
        }, []);
    });
}

var words1 = ["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"],
    words2 = ["Abc", "Cde", "Efa"];

console.log(getLongestWords(words1));
console.log(getLongestWords(words2));

.as-console-wrapper { max-height: 100% !important; top: 0; }

- Nina Scholz

---

对于变量 words = ["abc","cde","efa"]，输出应该是什么？ - mahbubcseju

@mahbubcseju，它可以与["Abc", "Cde", "Efa"]一起使用，并且您将获得三个结果集。 - Nina Scholz