문자열 벡터 정렬

Question

나는 정렬과 alogorithms을 많이 사용했지만 벡터는 괜찮습니다. 최근에 저는 흥미로운 질문에 직면 해 있으며 그것을 해결하는 방법에 대한 귀하의 제안을 원합니다. 그래서, 아래에 내 질문입니다.

Q, 나는 벡터에 4 개의 문자열을 부여 받았고 그 문자가 무엇인지에 따라 특정 순서로 정렬해야합니다. 따라서 모든 문자열의 마지막 문자는 다른 문자열의 첫 번째 문자와 일치해야하며이 문자열의 마지막 문자는 다른 문자열의 첫 번째 문자와 일치해야하며 가능한 한 가장 긴 문자열을 만들어야합니다.

예를 들어, "ABCD" "TGHI" "DADC" "IYUR" "CXYT" 과 같은 문자열 벡터가있는 경우 "ABCD"와 같이 정렬됩니다. 그러면 세 번째 문자열 "DADC"가 나타납니다. 다섯 번째 문자열 "CXYT"가 될 것입니다. 결과는 "ABCD" "DADC" "CXYT" "TGHI" "IYUR"가됩니다.

지금 위의 규칙에 따라 '호환 가능'하면 다른 문자열로 각 문자열을 확인하는 것이 좋을지 궁금합니다. 그렇다면 벡터에 5 개의 문자열이 있으면 5 개가됩니다. + 4 + 3 + 2 + 1 가능성이 있고 예를 들어 20 개의 문자열이 있다면 많은 양을 늘릴 수 있습니다. 이렇게 좋은 생각입니까 아니면 다른 좋은 효율적인 솔루션입니까? 감사합니다.) 당신은 이해합니다.

Answer 1

더 나은 방법은 문자열을 사용하여 유향 그래프를 작성하는 것입니다. s1의 마지막 문자가 s2의 첫 번째 문자와 같으면 문자열 s1에서 s2까지의 모서리가 있습니다. 그런 다음 그래프에서 가장 긴 경로를 찾으려고 할 수 있습니다.

Answer 2

모든 문자를 그래프의 노드로 상상해보십시오. 각 단어는 두 글자 사이의 경로를 나타냅니다. "ACCA"는 A -> A "BAAC"B -> C를 정의합니다. 이 그래프 내에서 오일러 경로를 찾고 싶습니다. http://en.wikipedia.org/wiki/Eulerian_path. Eulerian Path는 모든 가장자리를 정확히 한 번 방문하고 각 가장자리가 단어를 나타 내기 때문에 모든 단어를 사용했음을 의미합니다.