0

给定一些单词，例如香蕉、猫、狗、大象、类型、中间、湖

找到一个序列使得

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

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

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

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

我的想法：

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

但是，它是一个NP完全。

如何避免哈密顿路径？

有更好的主意吗？

谢谢

4

2 回答 2

1

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

于 2012-01-06T17:57:41.037 回答
0

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

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]] );
        }
    }
}
于 2012-01-06T21:51:13.593 回答