This post is completed by 2 users

  • 0
 Add to List
Medium

467. 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

Example:

Source = GUM
Target = MUG
Output: GUM -> UGM -> UMG -> MUG

Source: FRIED
Target: FIRED
FRIED -> RFIED -> RIFED -> IRFED -> IFRED -> FI

Approach: Recursion

  1. Given source and target strings.
  2. Maintain two lists, allCombinations and currentPath. 
  3. allCombinations - Will keep track of all the combinations that are tried for the source string. Maintaining this will prevent us from going to loops.
  4. currentPath - Will keep track of the current path, once the source reaches to target, we will print this.
  5. 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).
  6. Base Case: if source equals to target, print currentPath and return.

Output: 

Source: GUM
Target: MUG
GUM -> UGM -> UMG -> MUG

Related Problems: