Учитывая некоторые слова, найдите такую ​​последовательность, что любые смежные слова seq не могут иметь одинаковые символы

Question

Некоторые слова, например. банан, кошка, собака, слон, тип, средний, озеро

найти последовательность, чтобы

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

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

Если seq не найден, верните значение false. в противном случае верните true и seq.

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

Моя идея:

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

Но, это NP полный.

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

Любые лучшие идеи?

благодаря

Answer 1

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

Answer 2

Мой подход будет включать-структуру:

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

c1 будет первым символом ул и c2 будет последним. Я бы перебирал входной массив и генерировал узел для каждого элемента и, вероятно, помещал их в std :: vector. Затем на каждом узле push_back() ссылается на все узлы, которые могут быть корректно помещены перед этим узлом в действительные. Тогда я бы рекурсивно искал путь. Просто начните с первого узла, назовите его, перейдите к первому индексу valid, repeat для этого узла, затем, когда элемент управления вернется к этой точке, перейдите к следующему узлу в действительном порядке, выполните то же самое, затем, вернувшись отсюда, сбросьте использованное значение во всех узлах. Если совпадение не найдено, верните значение 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]]); 
     } 
    } 
}