Post
Ask Question

String Algorithm - Validating If String Conversion Requires More Than One Edits

Problem Statement

 
Write a program to validate how many edits (add, remove, or replace character) are required to convert a given string into another given string. You need to consider that comparison is case sensitive and whitespace is significant.
 
Example 1
 
Input: s1 = "bat" s2 = "bad"
 
Output
 
Only one edit is required to convert one string to another.
 
Explanation
 
One edit (character 't' needs to be replaced by 'd') is required to convert s1 into s2.
 
Example 2
 
Input: s1 = "belt" s2 = "bel"
 
Output
 
Only one edit is required to convert one string to another
 
Explanation
 
One edit (character 't' needs to be removed or deleted) is required to convert s1 into s2.
 
Example 3
 
Input: s1 = "sea" s2 = "seat"
 
Output
 
Only one edit is required to convert one string to another
 
Explanation
 
one edit (character 't' needs to be added) is required to convert s1 into s2.
 
Example 4
 
Input: s1 = "salt" s2 = "sa"
 
Output
 
more than one edit
 
Explanation
 
more than one edit (character 'l' and 't' need to be removed) is required to convert s1 into s2.
 
Example 5
 
Input: s1 = "Salt" s2 = "sal"
 
Output
 
More than one edit
 
Explanation 
 
More than one edit (character 't' needs to be removed and 'S' need to be replaced by 's') is required to convert s1 into s2.
 
Example 6
 
Input: s1 = "sea food" s2 = "seafoo"
 
Output
 
more than one edit
 
Explanation
 
more than one edit (character 'd' needs to be removed and ' ' need to be removed ) is required to convert s1 into s2. 
 
Solution
 
Look at the steps described for an algorithm
  • Compare the length of two strings and if the difference between these two strings is more than one character then print the result “more than one edit is required to convert one string to another” because to convert one string to another string more than one edits (add, remove, or replace character) are required.
  • Find out a longer and smaller string based on the length difference, if the difference is less than 0 then the second given string is the longer string OR if the difference is more than 0 then first given string is the longer string OR difference equals to 0 then both strings are of the same length
  • Convert both the given strings into an array of a type character
  • Declare a variable to store the count of edits required
  • Iterate through string character set while loop reaches the end of longer string length or end of smaller string length,

    • check the value of variable edit counter, if more than one edit is found then return failure signal and print the result “more than one edit is required to convert one string to another”
    • match the character of given strings (longer and smaller)

      • if character matches then increment the counter for both smaller and longer string index otherwise,
      • if the character does not match then do the following,

        • increment the index counter for longer string and
        • Increment the index counter for smaller string if and only if the length of smaller and longer is same
        • increment the edit counter

      • finally, print “only one edit is required to convert one string to another”  
  1. class Program {  
  2.  static void Main(string[] args) {  
  3.   Console.Write("Please enter first string to be processed: ");  
  4.   var firstInputString = Console.ReadLine();  
  5.   Console.WriteLine();  
  6.   Console.Write("Please enter second string to be processed: ");  
  7.   var secondInputString = Console.ReadLine();  
  8.   
  9.   if (CompareLength(firstInputString, secondInputString) == false) // if length difference is more than 1 then more than one edit is required.    
  10.   {  
  11.    Console.WriteLine("more than one edit");  
  12.   } else {  
  13.    Console.WriteLine(FindEditCount(firstInputString, secondInputString) == false ?  
  14.     "more than one edit is required to convert one string to another" :  
  15.     "only one edit is required to convert one string to another");  
  16.   }  
  17.   
  18.   Console.ReadLine();  
  19.  }  
  20.   
  21.  private static bool FindEditCount(string firstInputString, string secondInputString) {  
  22.   // find out longer and smaller string based on the length difference    
  23.   // difference is less than 0 then second given string is the longer string    
  24.   // OR difference is more than 0 then first given string is the longer string    
  25.   // OR difference equals to 0 then both string are of same length    
  26.   string longerString = firstInputString;  
  27.   string smallerString = secondInputString;  
  28.   int val = longerString.Length - smallerString.Length;  
  29.   
  30.   if (val < 0) {  
  31.    longerString = secondInputString;  
  32.    smallerString = firstInputString;  
  33.   }  
  34.   
  35.   int smallerStringIndex = 0;  
  36.   int longerStringIndex = 0;  
  37.   int editCount = 0;  
  38.   
  39.   char[] longerStringCharacterSet = longerString.ToCharArray();  
  40.   char[] smallerStringCharacterSet = smallerString.ToCharArray();  
  41.   
  42.   //continue iterate through string character set while loop reach at the end of longer string length or end of smaller string length    
  43.   while (longerStringCharacterSet.Length > longerStringIndex && smallerStringCharacterSet.Length > smallerStringIndex) {  
  44.    if (editCount > 1) return false; // if more than one edit found then return failure signal    
  45.   
  46.    //match character of given strings (longer and smaller) if character match then increment the counter for both smaller and longer string index    
  47.    if (longerStringCharacterSet[longerStringIndex] == smallerStringCharacterSet[smallerStringIndex]) {  
  48.     longerStringIndex++;  
  49.     smallerStringIndex++;  
  50.    } else {  
  51.     // if do not match always increment the index counter for longer string     
  52.     longerStringIndex++;  
  53.     if (val == 0)  
  54.      // if do not match and length of smaller and longer is same    
  55.      // then increment the index counter for smaller string too     
  56.      smallerStringIndex++;  
  57.     editCount++;  
  58.    }  
  59.   }  
  60.   
  61.   return true;  
  62.  }  
  63.   
  64.  /// <summary>    
  65.  /// Compare the length of two given strings.    
  66.  /// </summary>    
  67.  /// <param name="firstInputString">First given string</param>    
  68.  /// <param name="secondInputString">Second given string</param>    
  69.  /// <returns></returns>    
  70.  private static bool CompareLength(string firstInputString, string secondInputString) {  
  71.   return Math.Abs(firstInputString.Length - secondInputString.Length) <= 1;  
  72.  }  
  73. }  
Time Complexity
 
O(n )
 
array iteration takes O(n) time to iterate through n characters where n is the length of the string.
 
Note
Please feel free to propose or suggest a solution you might think can be followed to make it better and more optimized


Similar Articles