Given an array of Strings, return true if each string could be connected to other -

you given array of strings, return true if , if strings can connected in 1 chain.

condition connectivity is, if last character of 1 string matches first character of second string, 2 strings can connected.

example : string []arr ={"abc", "cde", "cad" , "def" , "eac"} return true because strings can connected in 1 chain.

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

another example: string []arr ={"acb" , "cde", "def", "ead" } returns false because
"cde"->"ead"->"def" possible chain “acb” left out.

note: it's not necessary start first string , form chain, may happen won’t chain if start first string. can chain if start other string. if there exists possible chain, solution should return true.

in second example, if first string suppose “fcb”, possible chain have existed, "cde"->"ead"->"def"->"fcb" true.

possible solution (what thinking): consider each string graph node , connect nodes if condition satisfied. once done, problem reduces finding,

if there exists hamiltonian cycle in graph, np-complete problem.

anyone suggest algorithm or other solutions?

your not looking hamiltonian cycle (ie beggining = start) hamiltonian path np-complete problem too. however, graphs not general 1 since there 26 letters. if allows more symbol 26 letters equivalent hamiltonian path finding.

here solution: should think converse way:

• the vertex of graph 26 letters.
• there edge between letter x , y each word starting x , ending y

therefore multigraph several word can start , end same letter. looking called eulerian path: path takes each edges 1 time. finding eulerian path polynomial problem (https://en.wikipedia.org/wiki/eulerian_path). 1 of first graph problem in history.

now citing wikipedia:

a directed graph has eulerian trail if , if @ 1 vertex has (out-degree) − (in-degree) = 1, @ 1 vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree , out-degree, , of vertices nonzero degree belong single connected component of underlying undirected graph.

this far better way decide if there path searching hamiltonian path.