Cho một chuỗi các chuỗi, trả về true nếu mỗi chuỗi có thể được kết nối với

Question

Bạn được cung cấp một chuỗi các chuỗi, trả về true nếu và chỉ khi tất cả các chuỗi có thể được kết nối trong một chuỗi.

Điều kiện kết nối là nếu ký tự cuối cùng của một chuỗi khớp với ký tự đầu tiên của chuỗi thứ hai, thì hai chuỗi có thể được kết nối.

Ví dụ: String []arr ={"abc", "cde", "cad" , "def" , "eac"} sẽ trả lại đúng vì tất cả các chuỗi có thể được kết nối trong một chuỗi.

"abc"->"cde"->"eac"->"cad"->"def" 

Một ví dụ khác: String []arr ={"acb" , "cde", "def", "ead" } lợi nhuận False vì
"cde"->"ead"->"def" là chuỗi có thể nhưng “acb” đang bị bỏ rơi.

Lưu ý: Không cần bắt đầu bằng chuỗi đầu tiên và tạo thành chuỗi, Có thể bạn sẽ không nhận được chuỗi nếu bạn bắt đầu bằng chuỗi đầu tiên. Bạn có thể nhận được một chuỗi nếu bạn bắt đầu với bất kỳ chuỗi nào khác. Nếu tồn tại một chuỗi có thể, thì giải pháp của bạn sẽ trả về true.

Trong ví dụ thứ hai, nếu Chuỗi đầu tiên được giả sử là “fcb”, sau đó một chuỗi có thể sẽ tồn tại, "cde"->"ead"->"def"->"fcb" nên Đúng.

GIẢI PHÁP CÓ THỂ HÓA (tôi đang nghĩ gì): Hãy xem xét từng chuỗi làm biểu đồ Nút và kết nối các nút nếu điều kiện được thỏa mãn. Khi đã hoàn tất, vấn đề sẽ giảm xuống khi tìm kiếm,

if there exists a Hamiltonian Cycle in a graph, đây là vấn đề NP-Complete.

Bất kỳ ai đề xuất một số thuật toán hoặc bất kỳ giải pháp nào khác?

Answer 1

Bạn không tìm đến chu kỳ Hamilton (tức là bắt đầu = bắt đầu) nhưng đường dẫn Hamilton cũng là vấn đề NP-Complete. Tuy nhiên, đồ thị của bạn không phải là đồ thị chung vì chỉ có 26 chữ cái. Nếu bạn cho phép biểu tượng nhiều hơn 26 ký tự thì nó thực sự tương đương với tìm đường dẫn Hamilton.

Đây là một giải pháp: bạn nên nghĩ cách ngược lại:

• đỉnh của đồ thị là 26 chữ cái.
• Có một cạnh giữa thư x và y cho mỗi từ bắt đầu với x và kết thúc với y

Do đó những gì bạn nhận được là thực sự là một multigraph như một số từ có thể bắt đầu và kết thúc bằng chữ giống nhau. Sau đó, những gì bạn đang tìm kiếm được gọi là một con đường Eulerian Eulerian: đó là một con đường mà mất mỗi cạnh chính xác một thời gian. Tìm một đường dẫn Euler là một vấn đề đa thức (https://en.wikipedia.org/wiki/Eulerian_path). Nó thực sự có lẽ là một trong những vấn đề đồ thị đầu tiên trong lịch sử.

Bây giờ trích dẫn Wikipedia:

Một đạo diễn đồ thị có một đường mòn Euler khi và chỉ khi nhiều nhất một đỉnh đã (out-độ) - (ở độ) = 1, ít nhất một đỉnh có (in-degree) - (out-degree) = 1, mỗi đỉnh khác có bằng nhau về mức độ và mức độ, và tất cả các đỉnh của nó với mức độ không đẳng cấp thuộc về một thành phần được kết nối duy nhất của biểu đồ không bị gạch dưới cơ bản.

Đây là cách tốt hơn để quyết định xem có đường dẫn nào hơn là tìm đường dẫn Hamilton hay không.

Answer 2

câu hỏi tương tự đã trả lời ở đây: Detecting when matrix multiplication is possible

Bạn có thể giải quyết nó như Euler vấn đề con đường đó là đơn giản hơn nhiều so với một Đường đi Hamilton.

Thay vì làm cho mỗi chuỗi thành một nút trong biểu đồ, hãy đặt từng chữ cái một nút trong biểu đồ. Thêm một cạnh đạo diễn giữa hai chữ cái nếu một chuỗi bắt đầu bằng chữ cái đầu tiên và kết thúc bằng chữ cái kia. Bây giờ việc tìm đường dẫn Eulerian trong biểu đồ này sẽ cung cấp cho bạn giải pháp cần thiết.

Answer 3

Giả sử rằng bạn có một bảng chữ cái kích thước 26.

Hãy nghĩ về lời nói của bạn như một đồ thị có hướng với 26 đỉnh tương ứng với tất cả các chữ {a, b, ..., z}.

Đối với mỗi từ bạn có, hãy thêm cạnh được hướng vào biểu đồ - từ chữ bắt đầu từ đó đến chữ cái kết thúc.

Sau đó, bạn đang tìm Đường dẫn Euler của biểu đồ này - đường dẫn truy cập mọi cạnh (chuyển qua từng từ của bạn) chính xác một lần.

Có định lý nổi tiếng:

Đồ thị có hướng G trên n đỉnh có đường dẫn Euler iff. ít nhất n-1 đỉnh có mức độ đến bằng mức độ đi.

Ngoài ra, có các thuật toán để tạo chuyến tham quan như vậy trong thời gian đa thức, ví dụ: thuật toán của Fleury.