Print all steps to convert one string to another string
Objective: Given two strings, source string and target string, which are permutation or anagram of each other. You are allowed two swap only consecutive characters. Write an algorithm to print all the steps ( all the swaps) which will lead the conversion of the source string to the target string.
NOTE: There could be multiple paths, you need to find any one path
Source = GUM Target = MUG Output: GUM -> UGM -> UMG -> MUG Source: FRIED Target: FIRED FRIED -> RFIED -> RIFED -> IRFED -> IFRED -> FI
- Given source and target strings.
- Maintain two lists, allCombinations and currentPath.
- allCombinations – Will keep track of all the combinations that are tried for the source string. Maintaining this will prevent us from going to loops.
- currentPath – Will keep track of the current path, once the source reaches to target, we will print this.
- Iterate through the string, for each consecutive characters at index i, j
- Swap characters at indexes i and j and generate new string newSource.
- Check if newSource is already tried ( part of allCombinations), if yes then skip it.
- Else add it to allCombinations and make a recursive call with source= newSource, allCombinations and currentPath (add new Source to currentPath).
- Base Case: if source equals to target, print currentPath and return.
Source: GUM Target: MUG GUM -> UGM -> UMG -> MUG
Top Companies Interview Questions..-
If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.