给定一些单词，找到一个序列，使得seq的任何相邻单词不能具有相同的字符
给出一些词，例如香蕉，猫，狗，大象，类型，中间，湖
找到这样的序列
（1）每个单词都在序列上
（2）任何相邻的单词不能有相同的字符。
如果找不到seq，则返回false。 否则，返回true和seq。
没有重复。 没有单词的排列。
我的想法：
设置图形，并使用哈密顿路径查找seq。
但是，这是一个完整的NP。
如何避免汉密尔顿路径？
还有更好的想法？
谢谢
请注意，如果您构建了一个部分序列，那么只有最后一个单词才能确定您可以继续使用哪个其他单词。 例如，如果你选择了“香蕉”和“狗”，你可以继续“类型”或“湖”（“湖”与“香蕉”碰撞并不重要，因为“湖”将与“狗”）。 由于你必须按照它们出现的顺序使用这些单词（如果我理解你的描述正确），你可以使用动态编程来解决问题“我能用最后一个词结束的最长的单词序列是什么？”
我的方法将涉及一个结构：
struct node{ char c1, c2; char* str; int used; int ind; std::vector valid; }; c1将是str中的第一个字符，c2将是最后一个字符。 我会循环输入数组并为每个项生成一个节点，并可能将它们放入std :: vector中。 然后在每个节点上，push_back（）引用所有可以有效放置在该节点前面的节点。 然后我会递归寻找路径。 刚开始使用第一个节点，使用标签，导航到第一个有效索引，重复该节点，然后当控制返回到该点时，转到下一个有效节点，执行相同操作，然后从此处返回时，重置所有节点中的已使用值。 如果未找到匹配项，则返回false。
这是一些代码。 它确保每个单词的第一个和最后一个字母不匹配。 修改符合条件的表达式以满足您的需要。
#include #include #include struct node{ char c1, c2; char* str; int used; int ind; std::vector valid; }; int ispath_rec( std::vector &nodes, int depth, int* returnarray ); int ispath( char** value, int valuec, int* returnarray ){ std::vector nodes; for( int i = 0; i < valuec; i ++ ){ node* a = new node; nodes.push_back(a); a->used = 0; a->str = value[i]; a->c1 = value[i][0]; a->c2 = value[i][strlen(value[i])-1]; a->ind = i; } for( int i = 0; i < valuec; i ++ ){ node* a = nodes[i]; for( int j = 0; j < valuec; j ++ ){ node* b = nodes[j]; if( b->c1 != a->c2 && b != a ) /*b->c1 != a->c2 is the qualifying expression*/ a->valid.push_back( b ); } } return ispath_rec( nodes, valuec, returnarray ); } int ispath_rec( std::vector &nodes, int depth, int* returnarray ){ if( depth <= 0 ) return 1; for( int i = 0; i < nodes.size(); i ++ ){ if( nodes[i]->used == 0 ){ nodes[i]->used = 1; *returnarray = nodes[i]->ind; if( ispath_rec( nodes[i]->valid, depth-1, returnarray + 1 ) == 1 ) return 1; nodes[i]->used = 0; } } return 0; } int main(){ char* tmp[] = {"hello","oeyh","aol", "loks", "sol"}; int rets[5]; if( ispath( tmp, 5, rets ) ){ for( int i = 0; i < 5; i ++ ){ printf(" %s ", tmp[rets[i]] ); } } }