algorithm - Transform one string to another string using BFS -

algorithm - Transform one string to another string using BFS -

there string characters can either ‘a’, ‘b’ or ‘$’, there 1 ‘$’ in string.

at each step, can modify string follows:

‘$’ can swapped adjacent character, illustration “a$ba” can changed either “$aba” or “ab$a”.

you can swap $ character next adjacent character if adjacent character different next adjacent character. (for illustration ‘aba$ab’ can converted ‘a$abab’ or ‘ababa$’, ‘ab$aab’ cannot converted ‘abaa$b’, because ‘a’ cannot jump on ‘a’).

you given 2 strings, initial state , final state (lengths same), have output minimum number of steps required alter string in initial state string in final state.

how solve problem using breadth first search ?

example: string s1 ,s2 ; input: s1 = a$b , s2 = ab$ output: 1 input: s1 = aba$a , s2 = $baaa output: 2

the problem can solved via breadth-first search follows, using c#-like pseudocode syntax.

string finalstate; (to assigned final state) int distancetofinalstate(string currentstate) { if (currentstate == finalstate) { homecoming 0; // end of recursion - strings match, distance 0 } else { int val1 = infinity; int val2 = infinity; int val3 = infinity; int val4 = infinity; if ($ not @ leftmost position of currentstate) val1 = distancetofinalstate(currentstate $ moved left); if ($ not @ rightmost position of currentstate) val2 = distancetofinalstate(currentstate $ move right); if ($ has 2 chars left it) val3 = distancetofinalstate(currentstate $ moved 2 chars left 2 skipped characters reversed); if ($ has 2 chars right it) val4 = distancetofinalstate(currentstate $ moved 2 chars right 2 skipped characters reversed); homecoming minumum of {val1, val2, val3, val4}; } }

the initial problem can solved evaluating distancetofinalstate(initialstate).

string algorithm graph breadth-first-search