Problem Statement | |||||||||||||
| A Hamiltonian path in an undirected graph with N vertices is a sequence of vertices A1, A2, ..., AN such that all Ai are pairwise distinct and for each i (1 < i &le N), there is an edge between vertices Ai-1 and Ai. A path starts at vertex A1 and visits each vertex of the sequence in order, ending at vertex AN. The cost of a path is the sum of the weights of the edges connecting the path's consecutive vertices.
You're given a graph where the i-th (0-based) vertex is labeled with String label[i]. There is an edge between each pair of vertices. The cost of the edge between vertices i and j is equal to length^2 (label[i]) + length^2 (label[j]) - length^2 (LCP (label[i], label[j]) ), where "^2" denotes squaring operation, length(X) is the length of string X and LCP(X,Y) is the longest common prefix of strings X and Y. Return the minimum possible cost of a Hamiltonian path which starts at vertex 0 and ends at vertex 1. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | A prefix of string S is a string that can be obtained by removing zero or more contiguous characters from the end of S. | ||||||||||||
| - | The longest common prefix of two strings A and B is the longest possible string which is a prefix of both A and B. | ||||||||||||
Constraints | |||||||||||||
| - | label will contain between 2 and 50 elements, inclusive. | ||||||||||||
| - | Each element of label will be between 1 and 50 characters long, inclusive. | ||||||||||||
| - | Each element of label will consist of lowercase letters ('a'-'z') only. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||