UVA 429 Solution - Word Transformation

UVA 429 Solution - Word Transformation


uva id: shoaib05
Accepted Time: 0.036

I used Edit_Distance and Floyd warshall algorithm.
Every word acts as a node. Two nodes are adjacent if their edit distance is One.

map, may ,mad are adjacent of each other. But pad and map are not adjacent because their edit distance is 2. But mad and pad are adjacent because their edit distance is 1.



Here has no link between may and pad, no link between map and pad.

Code:

#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<stdio.h>
#define COLUMN 210
#define INFINITE 100000
using namespace std;
int editDistance(string str1,string str2)
{
int table[11][11],length1,length2,i,j;
length1=str1.size();
length2=str2.size();
for(i=0;i<=length1;i++)
table[0][i]=i;
for(i=1;i<=length2;i++)
table[i][0]=i;
for(i=1;i<=length2;i++)
{
for(j=1;j<=length1;j++)
{
if(str2[i-1]==str1[j-1])
table[i][j]=table[i-1][j-1];
else
table[i][j]=min(table[i-1][j-1],min(table[i][j-1],table[i-1][j]))+1;
}
}
return table[length2][length1];
}
void floyd_warsall(int (*graph)[COLUMN],int row)
{
int i,j,k;
for(i=0;i<row;i++)
{
for(j=0;j<row;j++)
{
if(i!=j && graph[i][j]!=INFINITE)
{
for(k=0;k<row;k++)
{
if(j!=k && graph[i][k]!=INFINITE)
{
graph[j][k]=min(graph[j][k],graph[i][j]+graph[i][k]);
}
}
}
}
}
}
int main() 
{
map<string,int> mymap;
map<string,int>::iterator mit1,mit2;
int i,j,test_case,graph[COLUMN][COLUMN],len,node;
string str,str1,str2;
cin>>test_case;
while(test_case--)
{
mymap.clear();
node=0;
while(cin>>str)
{
if(str[0]=='*')
break;
mymap[str]=node++;
}
for(i=0;i<node;i++)
{
for(j=0;j<node;j++)
{
if(i==j)
graph[i][j]=0;
else
graph[i][j]=INFINITE;
}
}
for(mit1=mymap.begin();mit1!=mymap.end();mit1++)
{
for(mit2=mymap.begin();mit2!=mymap.end();mit2++)
{
if(mit1!=mit2)
{
if(editDistance(mit1->first,mit2->first)>1)
graph[mit2->second][mit1->second]=graph[mit1->second][mit2->second]=INFINITE;
else
graph[mit2->second][mit1->second]=graph[mit1->second][mit2->second]=1;
}
}
}
floyd_warsall(graph,node);
getchar();
while(getline(cin,str))
{
len=str.size();
if(len==0)
break;
i=0;
while(str[i]!=' ')
i++;
str1=str.substr(0,i);
str2=str.substr(i+1,len-i-1);
cout<<str1<<" "<<str2<<" "<<graph[mymap[str1]][mymap[str2]]<<endl;
}
if(test_case>0)
cout<<endl;
}
return 0;
}

Comments

  1. UnknownJune 18, 2020 at 10:03 AM

    sir,the consept is not clear to me..
    can you explain the logic by another example??

    ReplyDelete

Post a Comment

Popular posts from this blog

uva 679 - Dropping Balls Solution

uva 679 - Dropping Balls Solution Algorithm: 1. convert (position-1)  to binary and store it to a string. 2. make the binary string length equal to the (depth-1) by adding zero(0) at start of the string. 3. reverse the binary string. 4. convert binary string to integer + power(2,depth-1). Example: depth=7; position=4; covert 4-1= 3 to binary. binary string is 11. make the string length 7-1=6 by adding 0. Updated string 000011. reverse the binary string and string is now 110000 convert binary string(110000) to integer. value is 48. calculate power_value=pow(2,7-1)=pow(2,6)=64. Answer is = 48 + 64=112. Code in C++: #include<iostream> #include<string> #include<algorithm> using namespace std; string convertDecimalToBinary(int num){ string result; while(num!=0){ if(num%2==1) result.insert(0,1,'1'); else result.insert(0,1,'0'); num=num/2; } return result; } int convertBinaryToDecimal(string &n...
Read more

uva 481 - What Goes Up Solution

uva 481 - What Goes Up Solution #include<iostream> #include<vector> using namespace std; void binary_search(int *arr, int search_value, int start, int end, int &index){ if (start == end){ index = start; return; } int mid = (start + end) / 2; if (arr[mid] == search_value){ index = mid; return; } else if (arr[mid + 1] == search_value){ index = mid + 1; return; } else if (arr[mid]<search_value && arr[mid + 1]>search_value){ index = mid + 1; return; } else if (arr[mid] > search_value){ binary_search(arr, search_value, start, mid, index); } else{ binary_search(arr, search_value, mid + 1, end, index); } } void calculate_lis(vector<int>&arr,vector<int>&result){ int *temp, i, max = 0, j, index, n = arr.size(), *res; temp = new int[n]; res = new int[n]; temp[0] = 0; for (i = 1; i < n; i++){ if (arr[temp[max]] < arr[i]){ res[i] = temp[max]; max++; ...
Read more

uva-10077 Solution --- The Stern-Brocot Number System

#include<iostream> using namespace std; int main(){ int input_num,input_den,left_num,left_den,right_num,right_den,cur_num,cur_den; while(cin>>input_num>>input_den){ if(input_num==1 && input_den==1) break; left_num=0; left_den=1; right_num=1; right_den=0; cur_num=cur_den=1; while(true){ if(cur_num== input_num && cur_den==input_den) break; if(cur_num*input_den < cur_den*input_num){ cout<<"R"; left_num=cur_num; left_den=cur_den; cur_num+=right_num; cur_den+=right_den; }else{ cout<<"L"; right_num=cur_num; right_den=cur_den; cur_num+=left_num; cur_den+=left_den; } } cout<<endl; } return 0; }
Read more