Breadth First Search
Problem Statement :
Given a string , we are standing at the starting point and we have to reach end in minimum steps by following these rules:
- We can either jump to neighbour indices or,
- We can jump to a position with same value.
Solution Approach :
Idea is to consider every character index, as a vertex of a graph where there is an edge between next and previous indices (vertices) and also between the indices with same values.
Example : 1213 => string
By taking indices of the string as vertices, 0–2, 0–1, 1–0, 1–2, 2–3, these are the egdes of the graph. Notice there is a direct edge between 1 (at index 0) and 1(at index 2) as the values in the both indices are same.
We can go through some best websites to learn coding use bfs or breadth first search to traverse every vertex, as bfs guarantees the minimum steps (why?, since it moves level wise). As mentioned above we can make a graph with indices as vertices, with every adjacent index and index with same values, as an edge. Additionally, we can store the indices of every character, using a 2-D array with 10 rows (0-9) for values, where each row stores the index of the character with value same as row number.
We will use
visitedarray to keep track of the indices which is already visited so we visit every vertex once only. Now we just have to traverse through all the vertices and for every vertex
vstore the distance of every adjacent vertex
ausing distance array
- create a queue and push the current index now perform following operations untill the queue is empty:
- each time we pop a vertex
vfrom queue, (
v= queue.front() ), we will mark the vertex
vas visited (
- Iterate for all the adjacent vertices of
vand for every adjacent vertex
a, do following :
aas visited and update distance as,
ainto the queue.
ais not visited,
parent[v] != a.
- update the ans ( ans = min(ans,current cycle length) ).
- Now check if the previous and next index is visited or not, if not mark them as visited and push into the queue.
The time complexity of the above method is represented in the form of
Vis the number of verices and
Eis the number of edges.