Last Updated: 20 Feb, 2021
One Away
Moderate
Asked in companies
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
Approaches
- 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”.
- The idea behind this approach is to maintain a variable that keeps the count of mismatched characters and one pointer for each string and compare the characters at these places
- 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 and we can shift both pointers by one place to the right
- If the characters do not match, then we can perform one of the operations.
- If the length of the first string is more than that of the second string, we know that we have to delete a character from the first string and thus we can increase the count by 1 and can shift the pointer of the first string by one place to the right.
- If the length of the first string is less than that of the second string, we know that we have to insert a character into the first string and thus we can increase the count by 1 and can shift the pointer of the second string by one place to the right.
- If the length of the first string is equal to that of the second string, we know that we have to replace the character of the first string and thus we can increase the count by 1 and can shift the pointer of the first string as well as of the second string by one place to the right.
- If at any point, the value of the count variable becomes more than one, it means that we need to perform more than one operation and we can return false.
- We can keep traversing as long as both the pointers are within their respective range (i.e the length of the respective range). As soon as one of the pointers gets out of range, we can stop traversing.
- If any of the strings has an extra character at the end we can increase the count by 1.
- Finally, if the count is less than or equal to one, it means that string A can be converted into string B by performing any of those operations not more than once and we can return “true”, else it’s not possible and we return “false”.