c++ - 给定两个字谜词。交换一个单词(仅允许交换相邻的字母)以到达另一个单词

Question

这个问题已经有答案了:

Sorting a sequence by swapping adjacent elements using minimum swaps (2 个回答)

已关闭 8 年前。

这是面试问题

给定两个互为字母异位词的单词。交换一个单词(仅交换相邻的单词)允许的字母)到达另一个单词？

例如

given = abcd
target = dbac

到达 dbac

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

我想过用编辑距离来解决，但是编辑距离没有考虑到仅交换相邻的字母

应该采取什么方法来解决这个问题？

我的代码使用编辑距离

#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;

}

Answer 1

您可以使用图表上的广度优先搜索轻松解决此问题:

• 字符串是节点，
• 相邻转置是边
• 转置序列是路径

考虑到这一点，您可以使用 boost graph library 。或者，对于这个简单的问题，您可以使用带有 vector (用于转置序列)、列表(用于呼吸优先搜索)和算法的标准库:

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

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

使用这些标准数据结构，搜索功能将如下所示:

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; 
 }

然后您可以尝试使用以下算法:

  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";
  }