//-------------------------------------------------------------------------
/*
Problem Statement:
-------------------
Given two strings string_x and string_y, find the effort required to convert string_x into string_y.
Definition of Effort Required : Number of characters which needs to be ADDED or DELETED from
string_x inorder to convert string_x into string_y.
*/
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//----- file: stringconversioneffort.c ------------------------------------
//-------------------------------------------------------------------------
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//-------------------------------------------------------------------------
/*
//Function:
int find_effort(char *string_x, char *string_y, int *char_to_be_added, int *char_to_be_deleted)
//Parameters:
[in]string_x : source string to be converted
[in]string_y : destination string to which source string needs to be converted
[out]char_to_be_added : number of characters which needs to be added in source string.
[out]char_to_be_deleted : number of characters which needs to be deleted in source string.
//Return-Value:
total effort required
*/
//-------------------------------------------------------------------------
int find_effort(char *string_x, char *string_y, int *char_to_be_added, int *char_to_be_deleted)
{
int i, j;
int length_x = strlen(string_x);
int length_y = strlen(string_y);
int total_effort = -1;
if( (length_x == 0) && (length_y != 0) )
{
(*char_to_be_added) = length_y;
(*char_to_be_deleted) = 0;
total_effort = (*char_to_be_added) + (*char_to_be_deleted);
return total_effort;
}
else if( (length_x != 0) && (length_y == 0) )
{
(*char_to_be_added) = 0;
(*char_to_be_deleted) = length_x;
total_effort = (*char_to_be_added) + (*char_to_be_deleted);
return total_effort;
}
else if( (length_x == 0) && (length_y == 0) )
{
(*char_to_be_added) = 0;
(*char_to_be_deleted) = 0;
total_effort = (*char_to_be_added) + (*char_to_be_deleted);
return total_effort;
}
int **c = NULL;
c = (int**) malloc ((length_x + 1) * sizeof(int*));
for(i = 0; i <= length_x; ++i)
{
c[i] = (int*) malloc ((length_y + 1) * sizeof(int));
memset(c[i], 0, (length_y + 1));
}
for(i = 1; i <= length_x; ++i)
{
for(j = 1; j <= length_y; ++j)
{
if(string_x[i-1] == string_y[j-1])
{
c[i][j] = c[i-1][j-1] + 1;
}
else if(c[i-1][j] >= c[i][j-1])
{
c[i][j] = c[i-1][j];
}
else
{
c[i][j] = c[i][j-1];
}
}
}
for(i = 0; i <= length_x; ++i)
{
free(c[i]);
}
free(c);
(*char_to_be_added) = length_y - c[length_x][length_y];
(*char_to_be_deleted) = length_x - c[length_x][length_y];
total_effort = (*char_to_be_added) + (*char_to_be_deleted);
return total_effort;
}
void print_result(char *string_x, char *string_y, int total_effort, int char_to_be_added, int char_to_be_deleted)
{
printf("Effort Required to convert \n\"%s\" into\n\"%s\"\ntotal_effort = %d\ncharacters to be added = %d\ncharacters to be deleted = %d\n", string_x, string_y, total_effort, char_to_be_added, char_to_be_deleted);
}
int main(int argc, char *argv[])
{
if(argc != 3)
{
printf("ERROR\nbinary USAGE: [binary_path] [string_x] [string_y]\n");
return 0;
}
char string_x[1024];
char string_y[1024];
int total_effort = 0;
int char_to_be_added = 0;
int char_to_be_deleted = 0;
strcpy(string_x, argv[1]);
strcpy(string_y, argv[2]);
total_effort = find_effort(string_x, string_y, &char_to_be_added, &char_to_be_deleted);
print_result(string_x, string_y, total_effort, char_to_be_added, char_to_be_deleted);
return 0;
}
//-------------------------------------------------------------------------
//----- file: stringconversioneffort.c ------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ gcc -o sce stringconversioneffort.c
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//Outputs:
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce abcd abcde
Effort Required to convert
"abcd" into
"abcde"
total_effort = 1
characters to be added = 1
characters to be deleted = 0
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce abcde abc
Effort Required to convert
"abcde" into
"abc"
total_effort = 2
characters to be added = 0
characters to be deleted = 2
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce a1b2c3 ac
Effort Required to convert
"a1b2c3" into
"ac"
total_effort = 4
characters to be added = 0
characters to be deleted = 4
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
[stringconversioneffort]$ ./sce agd 4e
Effort Required to convert
"agd" into
"4e"
total_effort = 5
characters to be added = 2
characters to be deleted = 3
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
//Logic used:
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
Concept of Longest Common Subsequence [LCS] is used to solve the problem.
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
The value c[length_x][length_y] in above function stores length of LCS
of string_x and string_y. This LCS length helps in finding the effort required.
//-------------------------------------------------------------------------
//-------------------------------------------------------------------------
![[Settings]->[Account Info]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEg6a0HyRX0QVcBH5nQiru7mrITgqbgNA8h2QmPHlgjodW-ACGB8EIQ9keWicHTfKrSpM5oxpr2Ttl1PG7mnNRIY-Y4OJc7LC7IIN_i7luKlp056qDT0aOwBRJi1jgTzNteZ4JqL2uIy/s1600/Settings_AccountInfo_1.png "Settings, Account Info")
