Minimum cost to traverse from one index to another in the String | C ++ implementation of the above approach . ; function to find the minimum cost ; graph ; adjacency matrix ; initialising adjacency matrix ; creating adjacency list ; pushing left adjacent elelemt for index ' k ' ; pushing right adjacent element for index ' k ' ; queue to perform BFS ; visited array ; variable to store depth of BFS ; BFS ; number of elements in the current level ; inner loop ; current element ; popping queue ; base case ; checking if the current node is required node ; iterating through the current node ; updating depth ; Driver Code ; input variables ; function to find the minimum cost
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinCost ( string s , int i , int j ) { vector < vector < int > > gr ( 26 ) ; bool edge [ 26 ] [ 26 ] ; for ( int k = 0 ; k < 26 ; k ++ ) for ( int l = 0 ; l < 26 ; l ++ ) edge [ k ] [ l ] = 0 ; for ( int k = 0 ; k < s . size ( ) ; k ++ ) { if ( k - 1 >= 0 and ! edge [ s [ k ] - 97 ] [ s [ k - 1 ] - 97 ] ) gr [ s [ k ] - 97 ] . push_back ( s [ k - 1 ] - 97 ) , edge [ s [ k ] - 97 ] [ s [ k - 1 ] - 97 ] = 1 ; if ( k + 1 <= s . size ( ) - 1 and ! edge [ s [ k ] - 97 ] [ s [ k + 1 ] - 97 ] ) gr [ s [ k ] - 97 ] . push_back ( s [ k + 1 ] - 97 ) , edge [ s [ k ] - 97 ] [ s [ k + 1 ] - 97 ] = 1 ; } queue < int > q ; q . push ( s [ i ] - 97 ) ; bool v [ 26 ] = { 0 } ; int d = 0 ; while ( q . size ( ) ) { int cnt = q . size ( ) ; while ( cnt -- ) { int curr = q . front ( ) ; q . pop ( ) ; if ( v [ curr ] ) continue ; v [ curr ] = 1 ; if ( curr == s [ j ] - 97 ) return d ; for ( auto it : gr [ curr ] ) q . push ( it ) ; } d ++ ; } return -1 ; } int main ( ) { string s = " abcde " ; int i = 0 ; int j = 4 ; cout << findMinCost ( s , i , j ) ; }