По заданным словам найдите последовательность, в которой любые смежные слова последовательности не могут иметь одинаковые символы.

Question

Учитывая некоторые слова, например, банан, кошка, собака, слон, тип, середина, озеро

найти последовательность, такую, что

(1) каждое слово находится в последовательности

(2) любые соседние слова не могут иметь одинаковые символы.

Если последовательность не может быть найдена, верните false.в противном случае верните true и послед.

Не дублируется.Нет перестановок слов.

Моя идея:

Настройте график и используйте гамильтонов путь, чтобы найти последовательность.

Но, это NP, завершенный.

Как избежать гамильтонова пути?

Есть идеи получше?

спасибо

Answer 1

Обратите внимание, что если вы создали частичную последовательность, только последнее слово определяет, с какими другими словами вы можете продолжить последовательность.Например, если вы выбрали «банан» и «собака», вы можете продолжить с «тип» или «озеро» (не имеет значения, что «озеро» сталкивается с «бананом», потому что «озеро» будет смежным с"собака").Поскольку вы должны использовать слова в том порядке, в котором они появляются (если я правильно понимаю ваше описание), вы можете использовать динамическое программирование , чтобы решить проблему «какая самая длинная последовательность слов, которую я могу произвести, заканчивается на я й слово? "

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]] );
        }
    }
}