How to find whether to single insert or delete from a string would make two strings equal?

check if two strings differ by one character python
check if two strings can become same after a swap in one string
check if edit distance between two strings is one
check if edit distance between two strings is one leetcode
check if two strings differ by one character java

Write a function named single_insert_or_delete that accepts two strings as input arguments and returns:

  • 0 if the two strings match exactly.
  • 1 if the first string can become the same as the second string by inserting or deleting a single character. Notice that inserting and deleting a character is not the same as replacing a character.
  • 2 otherwise.

Capital letters are considered the same as lower case letters.

The code:

def single_insert_or_delete (input_str, input_str_1):
    str_1 = input_str.lower()
    str_2 = input_str_1.lower()
    if (str_1 == str_2):
        return 0

#Main Program
input_str = input("Enter a string 1: ")
input_str_1 = input("Enter a string 2: ")
result = single_insert_or_delete(input_str, input_str_1)
print(result)

My question here is: How to proceed further for checking whether to insert or delete the character or do both?

From my analysis we have to check first whether the words are equal in length and then go for checking the character of the words. But then how to go about if the lengths of the string do not match?

These are some examples in the above image.

Since I can't add a comment I will post here the answer.

def single_insert_or_delete(s1,s2):
    s1,s2 = s1.lower(), s2.lower()
    count = 0
    if s1 == s2:
        return 0
    elif len(s1) == len(s2):
        return 2
    elif len(s1) - len(s2) == -1:
        if s1 == s2[:-1]:
            return 1
        else:
            for i in range(len(s2)):
                if s1 == s2[:i] + s2[i+1:]:
                    return 1
            else:
               return 2
    elif len(s1) - len(s2) == 1:
        if s1[:-1] == s2 or s1[1:] == s2:
            return 1
        else:
            for i in range(len(s1)):
                if s2 == s1[:i] + s1[i+1:]:
                    return 1
            else:
                 return 2  

    else:
        return 2

Concatenation, What is the name of the operation when you want to append one string to the end of another string? Given two strings, find if first string is a subsequence of second; Check a given sentence for a given set of simple grammer rules; Print all possible strings that can be made by placing spaces; Find all distinct palindromic sub-strings of a given string; Check if a given sequence of moves for a robot is circular or not; Check if two given strings are isomorphic to each other

This should do the job:

>>> def f(s1, s2):
        s1, s2 = s1.lower(), s2.lower()
        if s1 == s2:
            return 0
        elif len(s1) == len(s2):
            return 2
        elif len(s1) - len(s2) == 1:
            if (s1[1:] == s2) or (s1[:-1] == s2):
                return 1
        elif len(s1) - len(s2) == -1:
            #skip one char from s2 and check if it matches s1
            for i in range(len(s2)):
                if s1 == s2[:i] + s2[i+1:]:
                     return 1
        else:
            return 2

>>> f('python', 'java')
2
>>> 
>>> f('book', 'boot')
2
>>> f('sin', 'sink')
1
>>> 
>>> f('dog', 'dog')
0
>>> 
>>> f('poke', 'spoke')
1
>>> 
>>> f('poker', 'poke')
1
>>> 
>>> f('programing', 'programming')
1

Basically,

  1. Checks if s1 and s2 are same, then return 0
  2. If not, then check if they have same lengths, meaning to get them equals, we need a replacement, which should return 2
  3. If their lengths is just one character difference, then we can either delete or insert or character depending which one is greater than the other.

Meta Strings | Practice, How do I remove a character from a string in C#? Given two strings, find if first string is a subsequence of second. Given two strings str1 and str2, find if str1 is a subsequence of str2. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements (source: wiki). Expected time complexity is linear.

def inner_rearrange_string(s1,s2):
    answer=2  # returns 2 by default
    #Jump one char from s2 and check if it matches s1
    for i in range(1,len(s2)-1):
        if s1 == s2[:i] + s2[i+1:]:
            answer=1
    return answer

def single_insert_or_delete(s1,s2):
    s1, s2 = s1.lower(), s2.lower()
    lent=len(s2)
    s1_lent=len(s1)
    number_of_mismatch=0 #Get the current number of mismatch
    if s1 == s2:
        return 0
    elif len(s1) == len(s2): #Are the lengths equal? 
        for c in range (0,len(s1)):
            if s1[c]==s2[c]:
                Ismatch=True
            else:
                Ismatch=False
                number_of_mismatch+=1 # Increment the number of mismatch character(s)
        if(number_of_mismatch==1):
            return 1                    # return 1 then
        elif number_of_mismatch>=2:
            return 2                    # return 2 then
    elif len(s1) - len(s2) == 1:   # Is s1 > s2
        if (s1[1:] == s2) or (s1[:-1] == s2):
            return 1
    elif len(s1) - len(s2) == -1:  # Is s1 < s2
        if(s1==s2[1:lent]) or (s1==s2[0:lent-1]):
            return 1
        elif inner_rearrange_string(s1,s2)==1:  # call another function
            return 1
        else:
            return 2

    else:
        return 2

C#, after specified position. This method can be overloaded by changing the number of arguments passed to it. Transform one string to another using minimum number of given operations Given two strings s1 and s2, write a function that will convert s1 to s2(if possible) by using only one opeartion. The operation is to pick any character from s1 and insert it at front of s1.

The output is wrong tho when:

single_insert_or_delete('the', 'that') The function returns:None (instead of 2)

Check if edit distance between two strings is one, An edit between two strings is one of the following changes. Add a character; Delete a character; Change a character. Given two string s1 and s2, find if s1 can​  Converting one string to other using append and delete last operations. Given an integer k and two strings str1 and str2 determine whether or not we can convert str1 to str2 by performing exactly k of the below operations on str1. a) Append a lowercase English alphabetic letter to the end of the str1.

def _instructor_function (s1,s2):
    s1=s1.lower()
    s2=s2.lower()
    if s1==s2:
        return 0
    if abs(len(s1)-len(s2))!=1:
        return 2

    if len(s1)>len(s2):
        # only deletion is possible
        for k in range(len(s2)):
            if s1[k]!=s2[k]:
                if s1[k+1:]==s2[k:]:
                    return 1
                else:
                    return 2
        return 1
    else: # s1 is shorter Only insertion is possible
        for k in range(len(s1)):
            if s1[k]!=s2[k]:
                if s1[k:]==s2[k+1:]:
                    return 1
                else:
                    return 2
        return 1

Meta Strings (Check if two strings can become same after a swap in , Meta strings are the strings which can be made equal by exactly one swap in any check if on swapping any of these two characters in any string would make  Given two strings X and Y, and two values costX and costY. We need to find minimum cost required to make the given two strings identical. We can delete characters from both the strings. The cost of deleting a character from string X is costX and from Y is costY. Cost of removing all characters from a string is same.

Cocoa in a Nutshell: A Desktop Quick Reference, Using NSMutableString // Create a mutable string from an immutable string NSString *str stringWithString:str]; // Append one string to another, ms is now "​Hello, World! Insert strings within a string // ms is now "He_garbage_llo, World! Using it returns YES if the ids of the two strings are equal (which implies that the  1. If length of str1 is 0, then we need to insert all characters of str2 into str1 to make them equal. Therefore, edit distance between str1 and str2 when str1 is empty is length of str2. 2. If length of str2 is 0, then we need to delete all characters of str1 to make it equal to str2.

Dynamic Programming, iven two strings, s1 and s2 and edit operations (given below). Replace – Replace one character by another. Else if last characters in both the strings are not same then we will try all the possible operations ( insert, replace, delete) and get the solution for rest of the string recursively for each possibility and pick the  Transform One String to Another using Minimum Number of Given Operation Given two strings A and B, the task is to convert A to B if possible. The only operation allowed is to put any character from A and insert it at front.

String.Remove Method (System), NET Framework, strings are zero-based. The value of the startIndex parameter can range from zero to one less than the length of the string instance. Note. This  Bash Strings Equal – In this tutorial, we shall learn how to check if two strings are equal in bash scripting.. Bash Strings Equal. To check if two strings are equal in bash scripting, use bash if statement and double equal to == operator.

Comments
  • If the lengths do not match, find the first character that is different. If adding the correct letter makes the whole string match, it is a match. If removing the incorrect letter makes the whole string match, it is a match. Otherwise, it is not a match.
  • Did the teacher not go through the problem in class? I guess they are asking you to implement the string matching algorithm, which is usually solved with dynamic programming.
  • I wonder why basically the same question has been asked repeatedly over the last couple of hours). Does that same teacher refer all the students to SO? :-)
  • @FrerichRaabe Almost certainly
  • @Dingo, I have updated the code, now should work with the reversed strings: s1 is programming and s2 is programing
  • this function returns none for the strings "sin" and "sink"
  • Please update your code there is some problem when I enter "poke" and "poker" as two strings.
  • @KaranThakkar .. Do accept the answer if you are happy with it.
  • Please explain a bit more your answer so others can understand it.