首页 > 试题广场 > 字符串的转换路径问题
[编程题]字符串的转换路径问题
  • 热度指数:249 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个字符串,记为start和to,再给定一个字符串列表list,list中一定包含to,list中没有重复的字符串。所有的字符串都是小写的。规定start每次只能改变一个字符,最终的目标是彻底变成to,但是每次变成新字符串必须在list中存在。请返回所有的最短的变换路径(按照字典序最小的顺序输出)。

输入描述:
输出包含多行,第一行包含一个整数n,代表list的中字符串的个数,第二行中包含两个字符串,分别代表start和to。接下来n行,每行一个字符串,代表lis[i](保证字符串长度都为3)。


输出描述:
如果存在转换的路径,请先输出“YES”,然后按照字典序最小的顺序输出所有路径。如果不存在请输出“NO”。
示例1

输入

8
abc cab
cab
acc
cbc
ccc
cac
cbb
aab
abb

输出

YES
abc -> abb -> aab -> cab
abc -> abb -> cbb -> cab
abc -> cbc -> cac -> cab
abc -> cbc -> cbb -> cab
1、将from加入到list中
2、根据list里面所有的字符串建图,每个字符串是图中的一个节点,相互之间只差一个字符的字符串节点之间有边相连
3、从to开始bfs,直到from,求出from到to的最短距离,bfs过程中没有遍历过的字符串一定不在最短路径上
4、从from开始dfs直到to,只有在最短路径上的字符串才会进行dfs,省去很多无用的dfs递归
发表于 2020-05-06 17:56:27 回复(0)
#include<cstdio>
#include<vector>
#include<iostream>
#include<unordered_map>
#include<string>
#include<climits>
#include<algorithm>
using namespace std;
int n;
string s, d;
vector<vector<string> > ans;
vector<string> temp;
int minstep = INT_MAX;
unordered_map<string, int> m, m1;
int cmp(vector<string> v1, vector<string> v2) {
	for (int i = 0; i < v1.size(); ++i) {
		if (v1[i] != v2[i])
			return v1[i] < v2[i];
	}
}
void dfs(string ss, int step) {
	if (step > minstep)
		return;
	temp.push_back(ss);
	if (ss == d)
	{
		if (step < minstep)
		{
			minstep = step;
			ans.clear();
			ans.push_back(temp);
		}
		else if (step == minstep) {
			ans.push_back(temp);
		}
		temp.pop_back();
		return;
	}
	for (int i = ss.size()-1; i >= 0; --i) {
		for (int j = 25; j >= 0; --j) {
			char tmp = ss[i];
			ss[i] = j + 'a';
			if (m[ss] == 0 && m1[ss] == 1) {
				m[ss] = 1;
				dfs(ss, step + 1);
				m[ss] = 0;
			}
			ss[i] = tmp;
		}
	}
	temp.pop_back();
}
int main() {
	string q;
	while (scanf("%d", &n) != EOF) {
		m.clear();
		m1.clear();
		ans.clear();
		temp.clear();
		minstep = INT_MAX;
		cin >> s >> d;
		for (int i = 0; i < n; ++i) {
			cin >> q;
			m1[q] = 1;
		}
		dfs(s, 0);
		if (ans.size() == 0)
			printf("NO\n");
		else {
			printf("YES\n");
			sort(ans.begin(), ans.end(), cmp);
			for (int i = 0; i < ans.size(); ++i) {
				for (int j = 0; j < ans[i].size(); ++j) {
					if (j == 0)
						cout << ans[i][j];
					else
						cout << " -> " << ans[i][j];
				}
				cout << endl;
			}
		}
	}
	return 0;
}

编辑于 2020-05-01 16:33:20 回复(0)
DFS超时,只能通过25%用例

#include<bits/stdc++.h>
using namespace std;
int strD(string s1, string s2) {
    int d=0;
    for(int i=0; i<3; i++) if(s1[i]!=s2[i]) d++;
    return d;
}
void dfs(vector<vector<string>> &ans, vector<string> &lis, vector<string> &tmp, vector<bool> &used, string last, string to, int pos, int d){
    
    if(tmp.size()==d-1 && strD(tmp[tmp.size()-1], to) == 1) {
        ans.push_back(tmp);
        return;
    }
    if(pos==d) return;
    for(int i=0; i<lis.size(); i++) {
        if(!used[i] && strD(last, lis[i])==1) {
            tmp.push_back(lis[i]);
            used[i]=true;
            dfs(ans, lis, tmp, used, lis[i], to, pos+1, d);
            tmp.pop_back();
            used[i]=false;
        }
    }
    return;
}

int main() {
    int n;
    cin>>n;
    string start, to, str;
    cin>>start>>to;
    vector<string> lis;
    vector<bool> used;
    for(int i=0; i<n; i++) {
        cin>>str;
        lis.push_back(str);
    }
    sort(lis.begin(), lis.end());
    used.resize(lis.size());
    for(int i=0; i<used.size(); i++) used[i]=false;
    vector<vector<string>> ans;
    vector<string> tmp;
    int d=strD(start, to);
    if(d<=1) cout<<"NO"<<endl;
    
    dfs(ans, lis, tmp, used, start, to, 0, d);
    
    if(ans.empty()) {
        cout<<"NO"<<endl;
        return 0;
    }
    else {
        cout<<"YES"<<endl;
        for(int i=0; i<ans.size(); i++) {
            cout<<start<<" -> ";
            for(int j=0; j<ans[i].size(); j++) {
                cout<<ans[i][j]<<" -> ";
            }
            cout<<to<<endl;
        }
    }
    return 0;
}
发表于 2020-03-25 12:59:51 回复(0)