Given two words which are anagrams. Swap one word (only adjacent swapping of letters allowed) to reach to the other word

Question

This is the interview question

Given two words that are anagram of each other. Swap one word (only adjacent swapping of letters allowed) to reach to the other word ?

for example

given = abcd
target = dbac

to reach dbac

[Given] abcd
[1]bacd
[2]badc
[3]bdac
[4]dbac

I thought of solving it using edit distance, but edit distance does n't take into account only adjacent swapping of letters

What should be the approach to solve this?

My code using edit distance

#define STRING_X "abcd"
#define STRING_Y "dbac"



// Returns Minimum among a, b, c
int Minimum(int a, int b, int c)
{
    return min(min(a, b), c);
}

// Recursive implementation
int EditDistanceRecursion( char *X, char *Y, int m, int n )
{
    // Base cases
    if( m == 0 && n == 0 )
        return 0;

    if( m == 0 )
        return n;

    if( n == 0 )
        return m;

    // Recurse
    int left = EditDistanceRecursion(X, Y, m-1, n) + 1;
    int right = EditDistanceRecursion(X, Y, m, n-1) + 1;
    int corner = EditDistanceRecursion(X, Y, m-1, n-1) + (X[m-1] != Y[n-1]);

    return Minimum(left, right, corner);
}

int main()
{
    char X[] = STRING_X; // vertical
    char Y[] = STRING_Y; // horizontal

    printf("Minimum edits required to convert %s into %s is %d by recursion\n",
           X, Y, EditDistanceRecursion(X, Y, strlen(X), strlen(Y)));

    return 0;

}

Perhaps this Wikipedia page section will inspire you. http://en.wikipedia.org/wiki/Transposition_(mathematics)#Transpositions — Pascal Cuoq, Aug 01 '14 at 21:57
http://stackoverflow.com/questions/20990127/sorting-a-sequence-by-swapping-adjacent-elements-using-minimum-swaps — indiv, Aug 01 '14 at 22:01
why so many negative votes. I just want to know how to solve this problem. I have also shared how I approached and tried solving the it. — v09, Aug 01 '14 at 22:02
If all you need is just mutate one word to another by swapping adjacent chars (and you don't care about number of swaps), you can reduce the task to bubble sort of the source string (using special comparing function, of course). It's pretty obvious approach, may be that's the reason for downvotes. — Vadim Kalinsky, Aug 01 '14 at 22:32
An obvious non-optimal solution is to swap each letter into its final position. — Jim Balter, Aug 02 '14 at 00:24
@JimBalter if you omit "only adjacent swapping of letters" rule, that solution becomes the most optimal one. — Vadim Kalinsky, Aug 02 '14 at 01:36
@VadimKalinsky Rather irrelevant since that rule is pretty much the whole point of the exercise. — Jim Balter, Aug 02 '14 at 02:15

score 0 · Answer 1 · answered Aug 02 '14 at 00:11

You may solve this easily using a breadth first search on a graph:

strings are nodes,
adjacent transposals are edges
sequence of transposals are paths

With that in mind, you could use the boost graph library. Or, for this simple problem, you could use standard library with vectors (for the sequence of transposals), lists (for the breath first search), and algorithms:

#include <string>
#include <list>
#include <vector>
#include <algorithm>
using namespace std; 

typedef vector<string> sequence;  // sequence of successive transpositions

With these standard data structures, the search function would look like:

vector<string> reach (string source, string target) 
{
  list<sequence> l;              // exploration list

  sequence start(1, source);     // start with the source
  l.push_back(start); 

  while (!l.empty()) {           // loop on list of candidate sequences 
    sequence cur = l.front();    // take first one 
    l.pop_front(); 
    if (cur[cur.size()-1]==target)  // if reaches target 
      return cur;                      // we're done !
                          // otherwhise extend the sequence with new transpos
    for (int i=0; i<source.size()-1; i++) { 
      string s=cur[cur.size()-1];     // last tranposition of sequence to extend
      swap (s[i], s[i+1]);            // create a new transposition
      if (find(cur.begin(), cur.end(), s)!=cur.end())
         continue;      // if new transpo already in sequence, forget it
      sequence newseq = cur;          // create extended sequence 
      newseq.push_back(s);
      if (s==target)                  // did we reach target ? 
         return newseq;
      else l.push_back(newseq);       // put it in exploration list
    }
  }
                      // If we're here, we tried all possible transpos,
  sequence badnews;   // so, if no path left, ther's no solution 
  return badnews; 
 }

You can then try the algorithm with the following:

  sequence r = reach ("abcd", "dbac");

  if (r.empty()) 
    cout << "Not found\n"; 
  else {
    for (auto x:r)
      cout<<x<<endl;
    cout <<r.size()-1<<" transpositions\n";
  }

Given two words which are anagrams. Swap one word (only adjacent swapping of letters allowed) to reach to the other word

1 Answers1