鉴于有些话，找一个序列，使得序列中的任何相邻的话不能有相同的字符 [英] Given some words, find a sequence such that any adjacent words of the seq cannot have same characters

问题描述

由于一些话， 例如 香蕉，猫，狗，大象，类型，中间，湖

Given some words, e.g. banana , cat , dog, elephant, type, middle, lake

找到一个序列，使得

（1）每一个字都是对的序列

(1) every word is on the sequence

（2）任何相邻的话不能有相同的字符。

(2) any adjacent words cannot have same characters.

如果该序列无法找到，返回false。否则，返回true，且起。

If the seq cannot be found, return false. otherwise, return true and the seq.

没有重复。话没有排列。

No duplicated. No permutations of words.

我的想法：

建立一个图，并用汉弥尔顿路径查找起。

Set up a graph, and use Hamiltonian path to find the seq.

不过，这是一个NP完全。

But, it is a NP complete.

如何避免哈密顿路径？

How to avoid Hamiltonian path ?

更好的想法？

感谢

推荐答案

请注意，如果你已经建立了一个部分序列，这仅仅是硬道理，它确定换句话说，你可以继续使用该序列。例如，如果你选择了香蕉和狗，你可能会继续与型或湖（也不要紧，湖与香蕉碰撞，因为湖将毗邻狗）。因为你必须使用它们出现的顺序的话（如果我没有理解你的描述），您可以使用动态规划要解决的问题是什么字的最长序列我可以产生与结束的我的日字？

Note that if you have constructed a partial sequence, it is only the last word that determines which other words you may continue the sequence with. For instance, if you have selected "banana" and "dog", you may continue with "type" or "lake" (it doesn't matter that "lake" collides with "banana", because "lake" will be adjacent to "dog"). Since you must use the words in the order they appear (if I understand your description correctly), you can use dynamic programming to solve the problem "what is the longest sequence of words I can produce that ends with the i th word?"

这篇关于鉴于有些话，找一个序列，使得序列中的任何相邻的话不能有相同的字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！