Problem Link: contest, practice
Difficulty: Simple
Pre-requisites: DFS, BFS, Graph traversal
Problem:
Given a graph G, 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:
Given a string S. Your task is to determine whether there is a walk W which realizes a given string S in graph G, and if so, find the lexicographically least such walk.
Explanation:
Let’s consider the picture from the statement carefully. The key observation is that there’s no vertex V in G such that it’s connected with two other vertices with the same letter written on them.
In other words, if we are looking for a way to continue the current walk from a vertex V and the next letter in S is C then two options are possible:
- V is not connected with vertices labled with C, so it’s impossible to continue the current walk;
- V is connected with exactly one vertex U labled with C, so there’s only one way to continue the current walk.
The next observation is that there are only two possible vertices to start our walk. After that observation we are ready to compose the whole solution:
- Choosing the starting vertex of the walk;
- Trying to complete the walk by moving to the corresponding vertices(if possible);
- Finding the lexicographically least valid walk. It’s sufficient to compare paths only by their starting vertices.
There is an interesting fact that the only situation when there are two valid paths is when S consists of one symbol concatenated several times with itself. For example, there are two valid paths 3838 and 8383 for S = DDDD.
Complexity is O(N) per a testcase.