Minimum Alteration String

 Coding Problem Keys 

 Minimum Alteration String 

 Problem Statement 

Given a set of N words, starting word and ending word, the words can be changed to obtain any one of the words in the given list of words by altering exactly one character and the target is to obtain the ending word with the minimum number of alterations starting with the starting word. Print the minimum number of alterations made to obtain the ending word.

 Boundary Condition(s) 

1 <= N <= 100

2 <= Length of words <= 100

 Input Format 

The first line contains N.

The next N lines contain the list of words.

The (N + 2)th line contains starting word

The (N + 3)th line contains ending word

 Output Format 

The first line contains the minimum number of alterations made to obtain the ending word.

 Example Input/Output 1 

 Input 

4

pep

pap

pat

pan

pen

pat

 Output 

2

 Explanation 

To change pen to pat.

4 alterations: pen ⟶ pep ⟶ pap ⟶ pan ⟶ pat

3 alterations: pen ⟶ pep ⟶ pap ⟶ pat

2 alterations: pen ⟶ pan ⟶ pat  

 Example Input/Output 2 

 Input 

3

line

lone

lane

life

lone

 Output 

2

 Output 

To change life to lone.

3 alterations: life ⟶ line ⟶ lane ⟶ lone

2 alterations: life ⟶ line ⟶ lone

 Note: Max Execution Time Limit: 5000 millisecs 

 Solution 

 Programming Language: C++ Language 

#include <bits/stdc++.h> 
using namespace std; 
int shortestChainLen( string start, string target, set<string>& D) { 
map<string, vector<string>> umap; 
for(int i = 0; i < start.size(); i++) { 
	string str = start.substr(0,i) + "*" +start.substr(i+1); 
	umap[str].push_back(start); 
}
for(auto it = D.begin(); it != D.end(); it++) { 
	string word = *it; 
	for(int j = 0; j < word.size(); j++) { 
	string str = word.substr(0,j) + "*" +word.substr(j+1); 
	umap[str].push_back(word); 
	} 
}
queue<pair<string, int>> q; 
map<string, int> visited; 
q.push(make_pair(start,1)); 
visited[start] = 1; 
while(!q.empty()){ 
	pair<string, int> p = q.front(); 
	q.pop(); 
	string word = p.first; 
	int dist = p.second; 
	if(word == target) { 
	return dist; 
	} 
	for(int i = 0; i < word.size(); i++) { 
	string str = word.substr(0,i) + "*" + word.substr(i+1); 
	vector<string> vect = umap[str]; 
	for(int j = 0; j < vect.size(); j++) { 
		if(visited[vect[j]] == 0) {
		visited[vect[j]] = 1; 
		q.push(make_pair(vect[j], dist + 1)); 
		} 
	} 
	} 
} 
} 
int main() {
	int n;
	cin>>n;
	string x,start,target;
	set<string> D;
	for(int i=0;i<n;i++){
		cin>>x;
		D.insert(x);
	}
	cin>>start;
	cin>>target;	
	cout << shortestChainLen(start, target, D)-1;
}
#Published By PKJCODERS

 (Note: Incase If the code doesn't Pass the output kindly comment us with your feedback to help us improvise.)