首页 > 试题广场 >

字符串的转换路径问题

[编程题]字符串的转换路径问题

热度指数：1037 时间限制：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

算法知识视频讲解

Java

柠檬茶c

import java.util.*;


public class Main {

    public static HashMap<String, TreeSet<String>> graph = new HashMap<>();
    public static ArrayList<String> nodes = new ArrayList<>();
    public static HashMap<String, TreeSet<String>> pre = new HashMap<>();
    public static ArrayList<ArrayList<String>> res = new ArrayList<>();
    public static HashMap<String, Integer> distance = new HashMap<>();

    public static class Pair {
        public String id;
        public Integer distance;

        public Pair(String id, Integer distance) {
            this.id = id;
            this.distance = distance;
        }
    }

    public static Comparator<Pair> disComparator = new Comparator<Pair>() {
        @Override
        public int compare(Pair o1, Pair o2) {
            return o1.distance-o2.distance;
        }
    };

    public static Comparator<String> charComparator = new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.compareTo(o2);
        }
    };

    public static Comparator<ArrayList<String>> listComparator = new Comparator<ArrayList<String>>() {
        @Override
        public int compare(ArrayList<String> o1, ArrayList<String> o2) {
            return o1.toString().compareTo(o2.toString());
        }
    };

    public static boolean isAdjoin(String a, String b) {
        if (a.length() != b.length()) return false;
        int differentCharCnt = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                differentCharCnt++;
            }
        }
        return differentCharCnt == 1;
    }

    public static boolean isExistPath(String start, String to) {
        PriorityQueue<Pair> queue = new PriorityQueue<>(disComparator);
        queue.offer(new Pair(start, 0));
        distance.put(start, 0);
        HashSet<String> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            Pair cur = queue.poll();
            if (visited.contains(cur.id)) continue;
            visited.add(cur.id);
            for (String next : graph.get(cur.id)) {
                if (!visited.contains(next)) {
                    if (distance.get(cur.id) + 1 < distance.get(next)) {
                        distance.put(next, distance.get(cur.id)+1);
                        pre.put(next, new TreeSet<>(charComparator));
                        pre.get(next).add(cur.id);
                    } else if (distance.get(cur.id) + 1 == distance.get(next)) {
                        pre.get(next).add(cur.id);
                    }
                    queue.offer(new Pair(next, distance.get(next)));
                }

            }
        }
        return distance.get(to) != Integer.MAX_VALUE;
    }

    public static void getMinPath(String start, String to, ArrayList<String> solution) {
        if (to.equals(start)) {
            solution.add(start);
            ArrayList<String> temp = new ArrayList<>();
            for (int i = solution.size()-1; i >= 0; i--) {
                temp.add(solution.get(i));
            }
            solution.remove(start);
            res.add(temp);
            return;
        }
        solution.add(to);
        for (String preNode : pre.get(to)) {
            getMinPath(start, preNode, solution);
        }
        solution.remove(to);
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        String start = input.next();
        String to = input.next();
        for (int i = 0; i < N; i++) {
            nodes.add(input.next());
        }
        nodes.add(start);

        // initialize
        for (String node : nodes) {
            graph.put(node, new TreeSet<>(charComparator));
            distance.put(node, Integer.MAX_VALUE);
        }

        // construct graph
        for (int i = 0; i < nodes.size(); i++) {
            for (int j = 0; j < nodes.size(); j++) {
                if (isAdjoin(nodes.get(i), nodes.get(j))) {
                    graph.get(nodes.get(i)).add(nodes.get(j));
                }
            }
        }
        if (isExistPath(start, to)) {
            System.out.println("YES");
            getMinPath(start, to, new ArrayList<>());
            res.sort(listComparator);
            for (ArrayList<String> path : res) {
                for (int i = 0; i < path.size(); i++) {
                    System.out.print(path.get(i));
                    if (i != path.size()-1) {
                        System.out.print(" -> ");
                    }
                }
                System.out.println();
            }
        } else {
            System.out.println("NO");
        }
    }
}

发表于 2020-09-15 13:44:28 回复(0)

kangsouth

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)

littlehug

字典顺序是否需要在建立next的时候就设好? 很好奇如何不靠着sorting做到next字典顺序?

发表于 2021-03-06 02:42:04 回复(1)

Java

helloxuanbao

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void getShortPaths(String cur, String to,
                              Map<String, List<String>> nexts,
                              Map<String, Integer> distances,
                              Deque<String> path, List<List<String>> res) {
        path.add(cur);
        if (cur.equals(to)) {
            res.add(new ArrayList<>(path));
            path.pollLast();
            return;
        }
        for (String next : nexts.get(cur)) {
            if (distances.get(next) == distances.get(cur) + 1) {
                getShortPaths(next, to, nexts, distances, path, res);
            }
        }
        path.pollLast();
    }

    public static Map<String, Integer> getDistance(String from, Map<String, List<String>> nexts) {
        Map<String, Integer> distances = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        distances.put(from, 0);
        queue.offer(from);
        visited.add(from);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            for (String s : nexts.get(cur)) {
                if (!visited.contains(s)) {
                    distances.put(s, distances.get(cur) + 1);
                    queue.offer(s);
                    visited.add(s);
                }
            }
        }
        return distances;
    }

    public static Map<String, List<String>> getNexts(List<String> words) {
        Map<String, List<String>> nexts = new HashMap<>();
        Set<String> wordSet = new HashSet<>(words);
        for (String s : words) {
            nexts.put(s, new ArrayList<>());
        }
        for (String s : words) {
            nexts.put(s, getNext(s, wordSet));
        }
        return nexts;
    }

    private static List<String> getNext(String word, Set<String> wordSet) {
        List<String> res = new ArrayList<>();
        char[] chs = word.toCharArray();
        for (char c = 'a'; c <= 'z'; c++) {
            for (int i = 0; i < word.length(); i++) {
                if (c != chs[i]) {
                    char t = chs[i];
                    chs[i] = c;
                    if (wordSet.contains(String.valueOf(chs))) {
                        res.add(String.valueOf(chs));
                    }
                    chs[i] = t;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] line = br.readLine().split(" ");
        String from = line[0];
        String to = line[1];
        List<String> words = new ArrayList<>();
        words.add(from);
        for (int i = 0; i < n; i++) {
            words.add(br.readLine());
        }
        Map<String, List<String>> nexts = getNexts(words);
        Map<String, Integer> distance = getDistance(from, nexts);
        Deque<String> path = new LinkedList<>();
        List<List<String>> res = new ArrayList<>();
        getShortPaths(from, to, nexts, distance, path, res);
        if (res.size() == 0) {
            System.out.println("NO");
            return;
        }
        System.out.println("YES");
        List<String> paths = new ArrayList<>();
        for (List<String> strs : res) {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < strs.size(); i++) {
                sb.append(strs.get(i));
                if (i != strs.size() - 1) {
                    sb.append(" -> ");
                }
            }
            paths.add(sb.toString());
        }
        Collections.sort(paths);
        for (String p : paths) {
            System.out.println(p);
        }
    }
}

发表于 2022-02-08 23:30:45 回复(0)

昆少少

#include<bits/stdc++.h>
using namespace std;

vector<string> getNext(string word, const unordered_set<string>& dict){
    vector<string> ret;
    for(char cur = 'a'; cur <= 'z'; ++cur){
        for(int i = 0; i<word.size(); ++i){
            if(word[i] != cur){
                char tmp = word[i];
                word[i] = cur;
                if(dict.count(word)){
                    ret.push_back(word);
                }
                word[i] = tmp;
            }
        }
    }
    return ret;
}

unordered_map<string,vector<string>> getNexts(vector<string>& words){
    unordered_set<string> dict(words.begin(), words.end());
    unordered_map<string, vector<string>> nexts;
    for(int i = 0; i<words.size(); ++i){
        nexts[words[i]] = getNext(words[i], dict);
    }
    return nexts;
}

unordered_map<string, int> getDistances(string start, const unordered_map<string,vector<string>>& nexts){
    unordered_map<string, int> distances;
    distances[start] = 0;
    queue<string> que;
    que.push(start);
    unordered_set<string> s;
    s.insert(start);
    while(!que.empty()){
        string cur = que.front();
        que.pop();
       for( string str:nexts.at(cur)){
            if(s.count(str)==0){
                distances[str] = distances[cur]+1;
                que.push(str);
                s.insert(str);
            }
        }
    }
    return distances;
}

void getShortestPaths(string cur, string to, const unordered_map<string, vector<string>>& nexts, const unordered_map<string,int>& distances, vector<string> solution, vector<vector<string>>& res){
    solution.push_back(cur);
    if(to.compare(cur)==0){
        res.push_back(solution);
    }else{
        for(string next:nexts.at(cur)){
            if(distances.at(next)==distances.at(cur)+1){
                getShortestPaths(next, to, nexts, distances, solution, res);
            }
        }
    }
}

vector<vector<string>> findMinPaths(string start, string to, vector<string> list){
    //把start加入list
    list.push_back(start);
    //根据list生成每一个字符串nexts信息
    unordered_map<string,vector<string>> nexts = getNexts(list);
    //从start字符串出发，利用nexts信息和宽度优先遍历的方式，求出每一个字符串到start的最短距离
    unordered_map<string, int> distances = getDistances(start, nexts);
    vector<string> pathList;
    vector<vector<string>> res;
    //收集路径
    getShortestPaths(start, to, nexts, distances, pathList, res);
    return res;
}

void myPrint(vector<string>& v){
    for(int i = 0; i<v.size(); ++i){
        if(i!=0){
            cout<<" -> ";
        }
        cout<<v[i];
    }
    cout<<endl;
}

int main(){
    int n;
    cin>>n;
    string start, to;
    cin>>start>>to;
    vector<string> list(n);
    for(int i = 0; i<n; ++i){
        list[i].resize(3);
        scanf("%s", &list[i][0]);
    }
    vector<vector<string>> ret = findMinPaths(start, to, list);
    sort(ret.begin(), ret.end());
    if(ret.size()>0){
        cout<<"YES"<<endl;
        for(vector<string> it:ret){
            myPrint(it);
        }
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

C++代码要使用，const & 进行一些优化，才可以通过，否则会有超时问题。

发表于 2022-02-21 15:12:04 回复(0)

肥肥的哈哈

//这道题直接bfs不能过，需要两遍bfs

#include <iostream>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <vector>
#include <set>
using namespace std;

void bfs(
         unordered_map<string, vector<string>> &edges,
         unordered_map<string, int> &dis, string &start){
    queue<string> q;
    unordered_set<string> se;
    q.push(start);
    se.insert(start);
    dis[start] = 0;
    while (!q.empty()){
        string s = q.front(); q.pop();
        for (string next : edges[s]){
            if (!se.count(next)){
                q.push(next);
                se.insert(next);
                dis[next] = dis[s] + 1;
            }
        }
    }
}
void bfs(unordered_map<string, vector<string>> &edges,
         unordered_map<string, int> &dis, 
         string &start, string &to,
         queue<string> &help,
         set<string> &ans){
    queue<string> q;
    q.push(start);
    help.push(start);
    while(!q.empty()){
        string s = q.front(); q.pop();
        if(s == to){
            ans.insert(help.front());
            help.pop();
        }else{
            for (string next : edges[s]){
                if (dis[next] == dis[s] + 1){
                    q.push(next);
                    help.push(help.front() + " -> " + next);
                }
            }
            help.pop();
        }
    }
}
int main(){
    int n;
    cin>>n;
    string start, to;
    cin>>start>>to;
    //构图
    //1.set表示点集,构造点集
    unordered_set<string> sets;
    sets.insert(start);
    while(n--){ 
        string s;
        cin>>s;
        sets.insert(s);
    }
    //2.构造边集
    unordered_map<string, vector<string>> edges;
    for (string s : sets){
        vector<string> v;
        for (int i = 0; i < 3; ++i){
            for (int j = 'a'; j <= 'z'; ++j){
                string t = s;
                t[i] = j;
                if (s != t && sets.count(t)){
                    v.push_back(t);
                }
            }
        }
        edges[s] = v;
    }
    //3.先利用bfs生成start到各个点的最短距离
    unordered_map<string, int> dis;
    bfs(edges, dis, start);
    //4.再利用bfs生成路径（其实用bfs可以直接求出来，只不过会多些无所谓的搜索，
    //导致内存爆了，我直接bfs到第12个用例爆内存了）
    set<string> ans;
    queue<string> q;
    bfs(edges, dis, start, to, q, ans);
    if (!ans.empty()){
        cout<<"YES"<<endl;
        for (string s : ans){
            cout<<s<<endl;
        }
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

发表于 2021-07-22 00:11:16 回复(0)

UncleFly

// 建图 + bfs求最短路 + dfs求相应的路径 + 排序输出字典序最小的路径
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
vector<int> h, e, ne;
vector<string> arr;
vector<vector<int>> ans;
int idx = 0;
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
vector<bool> st;
void dfs(vector<int> &res, int idx, int cur_dis, int min_distance, int e_idx){
    if(cur_dis > min_distance)
    {
        if(idx == e_idx){
            ans.push_back(res);
        }
        return;
    }
    for(int i = h[idx];~i;i = ne[i]){
        int j = e[i];
        if(!st[j]){
            st[j] = true;
            res.push_back(j);
            dfs(res, j, cur_dis + 1, min_distance, e_idx);
            res.pop_back();
            st[j] = false;
        }
    }
}

int main(){
    int n;
    cin>>n;
    string start ,end;
    cin>>start>>end;
    int e_index = -1;
    e.resize(n*n, 0);
    h.resize(n+1, -1);
    ne.resize(n*n, 0);
    st.resize(n+10, false);
    int s_index;
    for(int i = 0;i<n;i++)
    {
        string s;
        cin>>s;
        arr.push_back(s);
    }
    if(find(arr.begin(), arr.end(), start) != arr.end())
    {
        cout<<"YES"<<endl;
        cout<<start<<endl;
        return 0;
    }
    arr.push_back(start);
    n++;
    sort(arr.begin(), arr.end());
    for(int i = 0;i<n;i++)
    {
        if(arr[i] == start)
            s_index = i;
        else if(arr[i] == end)
            e_index = i;
    }
    for(int i = 0;i<n;i++)
        for(int j = i+1;j<n;j++){
           int cnt = 0;
            for(int k = 0;k<arr[i].size();k++){
                if(arr[i][k] != arr[j][k])
                    cnt++;
               }
             if(cnt  == 1)
               add(i, j), add(j, i);
        }
    queue<int> q;
    vector<int> dis(n+1, 0);
    q.push(s_index);
    int min_distance = 0;
    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        for(int i = h[cur];~i;i = ne[i]){
            int j = e[i];
            if(dis[j] == 0){
                q.push(j);
                dis[j] = dis[cur] + 1;
                if(j == e_index){
                    min_distance = dis[j];
                    break;
                }
            }
        }
    }
   // cout<<s_index<<" "<<e_index<<" "<<min_distance<<endl;
    if(min_distance>0){
        cout<<"YES"<<endl;
        vector<int> v;
        v.push_back(s_index);
        // 用min_distance dfs 
        dfs(v, s_index, 1,min_distance, e_index);
        sort(ans.begin(), ans.end());
        // cout<<arr[ans[0][ans[0].size()-1]]<<endl;
        for(int i = 0;i<ans.size();i++){
            for(int j = 0;j<ans[i].size()-1;j++)
                cout<<arr[ans[i][j]]<<" -> ";
            cout<<arr[ans[i][ans[i].size()-1]]<<endl;
        }
        
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}

发表于 2021-05-26 22:09:12 回复(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)

静静等待12

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)