推荐|【庞果英雄会】最小操作数

给了A、B两个单词和一个单词集合Dict，每个的长度都相同。我们希望通过若干次操作把单词A变成单词B，每次操作可以改变单词中的一个字母，同时，新产生的单词必须是在给定的单词集合Dict中。求所有行得通步数最少的修改方法。

举个例子如下：

Given: A = "hit" B = "cog"

Dict = ["hot","dot","dog","lot","log"]

Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]

即把字符串A = "hit"转变成字符串B = "cog"，有以下两种可能：

"hit" -> "hot" -> "dot" -> "dog" -> "cog"；

"hit" -> "hot" -> "lot" -> "log" ->"cog"。

我的思路如下：

广度优先方式建立多叉树（类似多叉树）。从开始给的字符开始，从字典中找相差一个字母的所有集合，都为开始字符的孩子节点，并将这些节点放到一个列表list中。然后对列表list中的每一个节点N，继续找相差一个字母的所有集合（不包含已经在树上，且深度低于当前处理层的节点），做为N的孩子节点。这样，以广度优先的方式来建立多叉树。最后遇到了单词B，把这一层处理完，就可以从树上倒推得到变化过程了（可行的变化可能有多个）。

根据例子中所给的字典建立多叉树的过程（先要将字符B加入到字典中）：

需要注意的是：

1 树是逐层建立起来的，也就是广度优先，而不是深度优先，例如第3层有dot和lot，先将dot和lot放到树上，再着手建立第4层。所以，需要一个辅助列表来保存每一层的的节点。以便于建立下一层。

2 为了保证树的建立过程中，不会出现倒回头的现象，所以已经添加到树上的节点需要标记，在我的代码中初始化节点的深度为-1，表示还未添加到树上。

3 树的两个分支可能包含同一个孩子节点，例如上面从第4层到第5层。cog节点有两个父节点，所以严格来说，这并不是一个树^_^ 另外，cog在处理dog节点的时候已经添加到树上，但是在处理log节点时，又处理了一次，看似于第2点矛盾，其实不然，因为dog和log是处在同一层的，为了记录所有可行的方案需要这样处理。

4 可以不记录节点的孩子节点情况，但是为了最后回溯结果，每个节点要记录自己的父节点（可能有多个父节点）。

5 回溯就比较简单了，用一个数组模拟栈，从节点B不停地往父节点方向走，记录所有可行路径。

具体还是看代码吧，我下面这个代码在庞果网提交并没有通过，应该还是有考虑不周的地方，恳请读者不吝赐教。


// MinOperationCount.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include 
#include 
#include 
#include 
#include 
using namespace std;
 
typedef struct _NODE
{
    vector vecParentNode;
    int nDeep;
    bool isEnd;
 
}NODE, *PNODE;
 
bool IsNear(const string & strDest, const string & strSource)
{
    int nLenDest    = strDest.length();
    int nLenSource  = strSource.length();
    if (nLenSource != nLenDest)
    {
        return false;
    }
    int nDiff = 0;
    for (int i = 0; i < nLenSource; i++)
    {
        if (strDest.at(i) != strSource.at(i))
        {
            nDiff++;
        }
    }
    if (1 == nDiff)
    {
        return true;
    }
    return false;
}
 
bool FindNearString(set &setStrFind, map &mapStrNode, int nDeep)
{
    bool bRet = false;
    set setStrNext;
    set::iterator itSet = setStrFind.begin();
    for ( ; itSet != setStrFind.end(); itSet++)
    {
        map::iterator it = mapStrNode.begin();
        for ( ; it != mapStrNode.end(); it++)
        {
            if ( (-1 == it->second.nDeep || nDeep == it->second.nDeep) && 
                 IsNear(*itSet, it->first))
            {
                it->second.nDeep = nDeep;
                it->second.vecParentNode.push_back(*itSet);
                setStrNext.insert(it->first);
                if (it->second.isEnd)
                {
                    bRet = true;
                }
            }
        }
    }
    setStrFind = setStrNext;
    return bRet;
}
 
void OutputArray(string* arrayPath, int nDeep, vector> &vecResult)
{
    vector vecStr;
    for (int i = nDeep-1; i >= 0; i--)
    {
        vecStr.push_back(arrayPath[i]);
    }
    vecResult.push_back(vecStr);
}
 
void Recur(string* arrayPath, int i, int nDeep, string &strCur, 
           map &mapStrNode, vector> &vecResult)
{
    arrayPath[i] = strCur;
    map::iterator it = mapStrNode.find(strCur);
    if (it == mapStrNode.end())
    {
        OutputArray(arrayPath, nDeep, vecResult);
        return;
    }
    for (int j = 0; j < (int)mapStrNode[strCur].vecParentNode.size(); j++)
    {
        i++;
        Recur(arrayPath, i, nDeep, mapStrNode[strCur].vecParentNode[j], mapStrNode, vecResult);
        i--;
    }
 
}
 
void GetMinPath(string &strBegin, string &strEnd, 
                set &setDict, vector> &vecResult)
{
    if (strBegin == strEnd)
    {
        return;
    }
    map mapStrNode;
    setDict.insert(strEnd);
    set::iterator it = setDict.begin();
    for ( ; it != setDict.end(); it++)
    {
        NODE node = {};
        node.nDeep = -1;// -1 代表还没有插入到树上
        node.isEnd = (*it == strEnd) ? true : false;
        mapStrNode[*it] = node;
    }
    //广度优先建立多叉树
    set setStrFind;
    setStrFind.insert(strBegin);
    int nDeep = 1;
    bool isFind = false;
    while (setStrFind.size() != 0 && !isFind)
    {
        isFind = FindNearString(setStrFind, mapStrNode, nDeep);
        nDeep++;
    }
    if (!isFind)
    {
        return;
    }
    string* arrayPath = new string[nDeep];
    int i = 0;
    Recur(arrayPath, i, nDeep, strEnd, mapStrNode, vecResult);
    delete [] arrayPath;
}
 
class Solution
{
public:
    vector> findLadders(string start, string end, set& dict)
    {
        vector> vecResult;
        GetMinPath(start, end, dict, vecResult);
        return vecResult;
    }
};
 
int _tmain(int argc, _TCHAR* argv[])
{
    string strBegin = "hit";
    string strEnd= "cig";
    set setDict;
    setDict.insert("hot");
    setDict.insert("git");
    setDict.insert("dot");
    setDict.insert("dog");
    setDict.insert("lot");
    setDict.insert("log");
    setDict.insert("cog");
    vector> vecResult;
    Solution so;
    vecResult = so.findLadders(strBegin, strEnd, setDict);
    vector>::iterator it = vecResult.begin();
    for ( ; it != vecResult.end(); it++)
    {
        vector::iterator itStr = it->begin();
        for ( ; itStr != it->end(); itStr++)
        {
            cout<<*itStr<<" ";
        }
        cout<<"\n";
    }
	return 0;
}

update:

经过特例测试，发现是没有考虑到开始字符串出现在字典中的情况，所以将85行代码：

if (it == mapStrNode.end())

修改为：

if (it == mapStrNode.end() || nDeep == i+1) 即可。

评论记录：