One Away

Posted: 20 Feb, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given two strings, string A and string B. Your task is to determine whether string A can be transformed into string B by performing only one of the following operations at most one (or maybe zero) time.

1. You can delete a character from any position.
2. You can replace a character with any other character.
3. You can insert a character at any position. 

Note :

1. The strings are non-empty.
2. The strings only contain lowercase English letters.
Input Format :
The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains a string A. 

The second line of each test case contains a string B.
Output Format :
For each test case print in a new line, “True” if string A can be transformed into string B or “False” if this can’t be done.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 100
1 <= |A| <= 10^4
1 <= |B| <= 10^4

Where where |A| represents the size of the string A and where |B| represents the size of the string B.

Time Limit: 1sec
Approach 1
  • The idea behind this approach is to run a loop through every index of the string A.
  • First,  we can check the difference between the lengths of the two strings. If this difference is more than 1, it means that we would need more than 1 operation to convert string A into string B, and hence we can simply return false.
  • If the character at position i of string A is equal to the character at position i of string B, then we don’t need to perform any operation.
  • If the characters do not match, then we can perform one of the operations.
  • If we replace the character of string A with the character at position i of string B, then the remaining substrings of A (starting at position i+1 and ending at last position) and string B (starting at position i+1 and ending at last position) should be the same.
  • If we delete the ith character of string A, then the substring of string A (starting at position i+1 and ending at last position) and the substring of string B (starting at position i and ending at last position) should be the same. This is because since we deleted ith character from string A, its length reduces by 1.
  • If we choose to insert a character at this position, then the substring of string A (starting at position i and ending at last position) and the substring of string B (starting at position i+1 and ending at last position) should be the same. This is because we inserted a character into string A, so the remaining characters shift one place to the right.
  • If the remaining substrings of both the strings are equal after performing any one of these operations, it means that we can transform string A into string B by performing that particular operation.
  • If all characters are equal, it means that the strings are already equal and we don’t need to perform any operation and we can simply return “True”.
Try Problem