일부 단어가 주어지면 seq의 인접한 단어가 같은 문자를 가질 수없는 시퀀스를 찾으십시오.

Question

일부 단어가 주어지면 과 같이 예를 들어. 바나나, 고양이, 개, 코끼리, 유형, 중간, 호수

는 시퀀스를 찾을 수 등이

(1) 모든 단어는 순서에

(2) 인접한 단어가 없습니다 같은 자입니다 .

seq을 찾을 수없는 경우 false를 반환합니다. 그렇지 않은 경우는 true 및 seq를 돌려줍니다.

중복되지 않음. 단어의 순열이 없습니다.

내 생각은 :

그래프를 설정하고 서열을 찾기 위해 해밀턴 경로를 사용합니다.

하지만 NP 완료되었습니다.

해밀턴 경로를 피하는 방법?

더 좋은 아이디어가 있습니까?

감사

Answer 1

이 부분 순서를 구축 한 경우, 그것은 당신이 순서를 계속 할 수있는 다른 어떤 단어를 결정하는 마지막 단어가 아니라 있습니다. 예를 들어 "바나나"와 "개"를 선택한 경우 "호수"가 "바나나"와 충돌하므로 "유형"또는 "호수"로 계속 진행할 수 있습니다 "개"). 단어를 표시된 순서대로 사용해야하므로 (정확하게 설명을 이해할 경우) dynamic programming을 사용하면 " 단어로 끝나는 단어 중에서 가장 길게 나오는 단어는 무엇입니까?"라는 문제를 해결할 수 있습니다.

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

(C1)는 STR의 첫 번째 문자가 될 것이며, C2는 마지막이 될 것입니다 :

Answer 2

내 방법은 구조체를 포함한다. 내가 입력 배열을 통해 루프 및 각 항목에 대한 노드를 생성하고 아마 표준 : : 벡터에 넣어. 그런 다음 각 노드에서 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]]); 
     } 
    } 
}