def same_string(s1, s2):
    '''(str, str) -> bool
    Return True iff s1 == s2
    REQ: len(s1) == len(s2)
    '''
    # base case: empty strings are equal
    if(s1 == "" and s2 == ""):
        result = True
    # if we found a place where they're different, return False
    elif(s1[0] != s2[0]):
        result = False
    #if the first two letters are the same, look at the rest of the string
    else:
        result = same_string(s1[1:], s2[1:])
    return result

def almost_same_string(s1, s2):
    '''(str, str) -> bool
    Return True iff differ in at most one place
    REQ: len(s1) == len(s2)
    '''
    # base case: empty strings are equal
    if(s1 == "" and s2 == ""):
        result = True
    # if we found a place where they're different, the only way
    # we can return True is if the rest of the string is exactly equal
    elif(s1[0] != s2[0]):
        result = same_string(s1[1:], s2[1:])
    # if the first two letters are the same, then we need to check
    # if the rest of the strings are almost the same
    else:
        result = almost_same_string(s1[1:], s2[1:])
    return result

## solution using a helper function
def _almost_same_string_helper(s1, s2):
    '''(str, str) -> bool
    Return the number of places where s1 and s2 differ
    REQ: len(s1) == len(s2)
    '''
    # base case: empty strings differ in zero places
    if(s1 == "" and s2 == ""):
        result = 0
    # we have at least 1 character
    else:
        # count the number of differences in the first character
        if(s1[0] == s2[0]):
            differences = 0
        else:
            differences = 1
        # add the number of differences in the rest of the string
        differences += _almost_same_string_helper(s1[1:], s2[1:])
        result = differences
    return result




def almost_same_string2(s1, s2):
    '''(str, str) -> bool
    Return True iff differ in at most one place
    REQ: len(s1) == len(s2)
    '''
    return _almost_same_string_helper(s1, s2) <= 1


if(__name__ == "__main__"):
    print(same_string("ABCD", "ABCD"))
    print(same_string("ABXD", "ABCD"))
    print(same_string("ABCD", "WXYZ"))
    print(almost_same_string("ABCD", "ABCD"))
    print(almost_same_string("ABXD", "ABCD"))
    print(almost_same_string("ABCD", "WXYZ"))
    print(almost_same_string2("ABCD", "ABCD"))
    print(almost_same_string2("ABXD", "ABCD"))
    print(almost_same_string2("ABCD", "WXYZ"))