The following graph G is called a Petersen graph and its vertices have been numbered from 0 to 9. Some letters have also been assigned to vertices of G, as can be seen from the following picture:
Let’s consider a walk W in graph G, which consists of L vertices W1, W2, …, WL. A string S of L letters 'A' – 'E' is realized by walk W if the sequence of letters written along W is equal to S. Vertices can be visited multiple times while walking along W.
For example, S = 'ABBECCD' is realized by W = (0, 1, 6, 9, 7, 2, 3). Determine whether there is a walk W which realizes a given string S in graph G, and if so then find the lexicographically least such walk. The only line of input contains one string S. If there is no walk W which realizes S, then output -1 otherwise, you should output the least lexicographical walk W which realizes S.
Input : s = 'ABB' Output: 016 Explanation: As we can see in the graph the path from ABB is 016. Input : s = 'AABE' Output :-1 Explanation: As there is no path that exists, hence output is -1.
We apply breadth first search to visit each vertex of the graph.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.