Given some words, find a sequence such that any adjacent seq words cannot have the same characters

Question

Given some words, for example, banana, cat, dog, elephant, type, middle, lake

we find a sequence such that

(1) each word is in sequence

(2) any adjacent words may not have the same characters.

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

No duplication. There are no permutations of words.

My idea:

Set up the graph and use the Hamiltonian path to search for seq.

But this is a complete NP.

How to avoid the Hamiltonian path?

Any better ideas?

thanks

Answer 1

, , , . , "" "", "" "" (, "" "", "" "" ). , ( ), , " , , i- ?"

Answer 2

:

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

c1 str, c2 - . node , , std::vector. node, push_back() , node in valid. . node, , valid, repeat node, , , node , , reset . , 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]] );
        }
    }
}