给定一些单词，找到一个序列，使得该序列的任何相邻单词不能具有相同的字符

Question

给出一些话， 例如 banana、cat、dog、elephant、type、middle、lake

找到一个序列，使得

(1) 每个单词都在序列上

(2) 任何相邻单词不能具有相同的字符。

如果找不到 seq，则返回 false。否则，返回 true 和 seq。

无重复。没有单词的排列。

我的想法：

建立一个图，并使用哈密顿路径来找到序列。

但是，它是一个NP完全的。

如何避免哈密顿路径？

还有更好的想法吗？

谢谢

Answer 1

请注意，如果您构建了部分序列，则只有最后一个单词才能确定您可以使用哪些其他单词来继续该序列。例如，如果您选择了“香蕉”和“狗”，则可以继续选择“类型”或“湖”（“湖”与“香蕉”碰撞并不重要，因为“湖”将与“湖”相邻） “狗”）。由于您必须按照单词出现的顺序使用单词（如果我正确理解您的描述），您可以使用 动态编程 来解决“我能生成的以第 i 个单词结尾的最长单词序列是什么？”的问题。

Answer 2

我的方法将涉及一个结构：

struct node{
    char c1, c2;
    char* str;
    int used;
    int ind;
    std::vector<struct node*> valid;
};

c1 将是 str 中的第一个字符，c2 将是最后一个。我将循环输入数组并为每个项目生成一个节点，并可能将它们放入 std::vector 中。然后在每个节点上，push_back() 对可以有效放置在该节点前面的所有节点的引用有效。然后我会递归地寻找路径。只需从第一个节点开始，标记它使用的，导航到有效的第一个索引，重复该节点，然后当控制返回到该点时，转到有效的下一个节点，执行相同的操作，然后从这里返回时，重置所有节点中使用的值。如果未找到匹配项，则返回 false。

这是一些代码。它确保每个单词的第一个和最后一个字母不匹配。修改限定表达式以满足您的需要。

#include<stdio.h>
#include<string.h>
#include<vector>

struct node{
    char c1, c2;
    char* str;
    int used;
    int ind;
    std::vector<struct node*> valid;
};

int ispath_rec( std::vector<node*> &nodes, int depth, int* returnarray );

int ispath( char** value, int valuec, int* returnarray ){
    std::vector<node*> 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<struct node*> &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]] );
        }
    }
}