Solving 'is one away' with set()

Question

I am taking a Udemy course. The problem I am working on is to take two strings and determine if they are 'one edit away' from each other. That means you can make a single change -- change one letter, add one letter, delete one letter -- from one string and have it become identical to the other.

Examples:

s1a = "abcde"
s1b = "abfde"

s2a = "abcde"
s2b = "abde"

s3a = "xyz"
s3b = "xyaz"

• s1a changes the 'c' to an 'f'.
• s2a deletes 'c'.
• s3a adds 'a'.

The instructors solution (and test suite):

def is_one_away(s1, s2):
    if len(s1) - len(s2) >= 2 or len(s2) - len(s1) >= 2:
        return False
    elif len(s1) == len(s2):
        return is_one_away_same_length(s1, s2)
    elif len(s1) > len(s2):
        return is_one_away_diff_lengths(s1, s2)
    else:
        return is_one_away_diff_lengths(s2, s1)


def is_one_away_same_length(s1, s2):
    count_diff = 0
    for i in range(len(s1)):
        if not s1[i] == s2[i]:
            count_diff += 1
            if count_diff > 1:
                return False
    return True


# Assumption: len(s1) == len(s2) + 1
def is_one_away_diff_lengths(s1, s2):
    i = 0
    count_diff = 0
    while i < len(s2):
        if s1[i + count_diff] == s2[i]:
            i += 1
        else:
            count_diff += 1
            if count_diff > 1:
                return False
    return True


# NOTE: The following input values will be used for testing your solution.
print(is_one_away("abcde", "abcd"))  # should return True
print(is_one_away("abde", "abcde"))  # should return True
print(is_one_away("a", "a"))  # should return True
print(is_one_away("abcdef", "abqdef"))  # should return True
print(is_one_away("abcdef", "abccef"))  # should return True
print(is_one_away("abcdef", "abcde"))  # should return True
print(is_one_away("aaa", "abc"))  # should return False
print(is_one_away("abcde", "abc"))  # should return False
print(is_one_away("abc", "abcde"))  # should return False
print(is_one_away("abc", "bcc"))  # should return False

When I saw the problem I decided to tackle it using set().

I found this very informative: Opposite of set.intersection in python?

This is my attempted solution:

def is_one_away(s1, s2):
    if len(set(s1).symmetric_difference(s2)) <= 1:
        return True

    if len(set(s1).symmetric_difference(s2)) == 2:
        if len(set(s1).difference(s2)) == len(set(s2).difference(s1)):
            return True
        return False
    return False

When I run my solution online (you can test within the course itself) I am failing on the last test suite item:

False != True : 
Input 1: abc
Input 2: bcc
Expected Result: False
Actual Result: True

I have tried and tried but I can't get the last test item to work (at least not without breaking a bunch of other stuff).

There is no guarantee that I can solve the full test suite with a set() based solution, but since I am one item away I was really wanting to see if I could get it done.

Answer 1

This fails to pass this test, because you only look at unique characters:

>>> s1 = 'abc'
>>> s2 = 'bcc'
>>> set(s1).symmetric_difference(s2)
{'a'}

That's a set of length 1, but there are two characters changed. By converting to a set, you only see that there is at least one 'c' character in the s2 input, not that there are now two.

Another way your approach would fail is if the order of the characters changed. 'abc' is two changes away from 'cba', but your approach would fail to detect those changes too.

You can't solve this problem using sets, because sets remove two important pieces of information: how many times a character appears, and in what order the characters are listed.

Answer 2

Here's a solution using differences found by list comprehension.

def one_away(s1, s2):
    diff1 = [el for el in s1 if el not in s2]
    diff2 = [el for el in s2 if el not in s1]
    if len(diff1) < 2 and len(diff2) < 2:
        return True
    return False

Unlike a set-based solution, this one doesn't lose vital information about non-unique characters.

Answer 3

Here is solving one away where set is used to find the unique character. Done not completely using set but set is used to find the unique character in two given strings. List as a stack is used to pop item from both stacks, and then to compare them.

Using stack, pop items from both items and see if they match. Find the unique character item, and when popped item matches with unique character, we need to pop first string again.

For example, pales and pale when s is found, we should pop again. pales pale would be true because s is unique char and when s is popped, we will pop string1 again. If unmatched popped chars greater than 1 then we can return False.

def one_away(string1: str, string2: str) -> bool:
    string1, string2 = [ char for char in string1.replace(" ","").lower() ], [ char for char in string2.replace(" ","").lower() ]
    if len(string2) > len(string1):
        string1, string2 = string2, string1
    len_s1, len_s2, unmatch_count = len(string1), len(string2), 0

    if len_s1 == len_s2 or len_s1 - len_s2 == 1:
        unique_char = list(set(string1) - set(string2)) or ["None"]
        if unique_char[0] == "None" and len_s1 - len_s2 == 1:
            return True # this is for "abcc" "abc"
        while len(string1) > 0:
            pop_1, pop_2 = string1.pop(), string2.pop()
            if pop_1 == unique_char[0] and len_s1 - len_s2 == 1: 
                pop_1 = string1.pop()
            if pop_1 != pop_2:
                unmatch_count += 1
            if unmatch_count > 1:
                return False
        return True
    return False

For example test:

strings = [("abc","ab"), ("pale", "bale"), ("ples", "pale"), ("palee", "pale"), ("pales", "pale"), ("pale", "ple"), ("abc", "cab"), ("pale", "bake")]
for string in strings:
    print(f"{string} one_away: {one_away(string[0]), string[1]}")

('pale', 'bale') one_away: True
('ples', 'pale') one_away: False
('palee', 'pale') one_away: True
('pales', 'pale') one_away: True
('pale', 'ple') one_away: True
('abc', 'cab') one_away: False
('pale', 'bake') one_away: False