首页 > 试题广场 >

字符串变换

[编程题]字符串变换

热度指数：4428 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个string数组dic及数组大小n，同时给定字典中的两个字符串串s和串t，为将s变到t，每次可以改变s中的任意一个字符，请返回由s到t变换所需的最少步数。同时需要满足在变换过程中的每个串都是字典中的串。若无法变换到t则返回-1。保证字符串长度均小于等于10，字典中字符串数量小于等于500。

测试样例：

["abc","adc","bdc","aaa”],4,”abc","bdc"

返回：2

算法知识视频讲解

推荐

念润

思路：

最短搜索路径，所以是广度优先搜索(BFS)。

按照定义，存在一个字母差异的单词为邻居，因此采用逐位替换字母并查找字典的方法寻找邻居。

对队列中的每个单词记录路径长度。queue<pair<string,int> > q; 从start进入队列记作1.长度为i的字母的邻居，如果没有访问过，则路径长度为i+1

代码：

class Change {
public:
    int countChanges(vector<string> dic, int n, string s, string t) {
        vector<string>::iterator ite = find(dic.begin(),dic.end(),s);
        int result = BFS(s,t,dic);
        if(ite != dic.end()){
            --result;
        }//if
        return result;
    }
private:
    int BFS(string start,string end,vector<string> &dict){
        if(start == end){
            return 0;
        }//if
        // 存放单词和单词所在层次
        queue<pair<string,int> > q;
        q.push(make_pair(start,1));
        // 判断是否访问过
        vector<string> visited;
        visited.push_back(start);
        while(!q.empty()){
            pair<string,int> cur = q.front();
            q.pop();
            string word = cur.first;
            int size = word.size();
            // 穷尽所有可能的变换
            for(int i = 0;i < size;++i){
                string newWord(word);
                // 每次只变换一个字符 有26种可能
                for(int j = 0;j < 26;++j){
                    newWord[i] = 'a'+j;
                    // 找到目标返回
                    if(newWord == end){
                        return cur.second + 1;
                    }//if
                    // 判断之前访问过或者是否在字典里
                    vector<string>::iterator ite = find(dict.begin(),dict.end(),newWord);
                    vector<string>::iterator ite2 = find(visited.begin(),visited.end(),newWord);
                    if(ite2 == visited.end() && ite != dict.end()){
                        visited.push_back(newWord);
                        q.push(make_pair(newWord,cur.second+1));
                    }//if
                }//for
            }//for
        }//while
        return -1;
    }
};

编辑于 2015-08-18 16:26:57 回复(4)