Python Forum
Find Mismatch Between Two Strings
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Find Mismatch Between Two Strings
#1
Hello,

Please help me with this:

The function has two parameters, str1 and str2, and should return:

0 if both are identical (Dog and dog)
1 if there is one single different character and if you add/remove that, makes the two strings identical("spoke" and "poke", "poke" and "poker")
2 if the strings are not identical and cannot make them by adding/removing one character ("Java" and "Python", "Book" and "Boot")

All above are case-insensitive.

Thank you in advance.
Reply
#2
Show us your work so far. We will help, but we won't do your homework for you
Reply
#3
How would you solve this problem? You better come up with some ideas because nobody here is going to solve it for you.

Write "crate" and "create" on a sheet of paper.
Output:
crate create
Are the words similar? Do they pass your "can be same by adding/removing one letter" test? If they are, how did you determine that? If not, how did you determine that?

I would start by cleaning up the logic a little bit. I do not want to test if adding a letter will make the words the same, or if subtracting a letter will make them the same. That sounds like too much work. I am going to have three tests.

1. The words do not match if the difference in word length is greater than 1.
2. The words match if they are identical.
3. The words match if I can add 1 letter to the shorter word and make it match the longer word.

Tests 1 and 2 are really easy to apply. Looking at "crate" and "create" I see the lengths differ by 1, so they pass test 1. I compare the words letter by letter 'c' = 'c', 'r' = 'r', 'a' != 'e'. The words are not identical, so they fail test 2. That means I have to perform test 3.

Test 3 is obviously the trickiest test. You will have to think about it a while with your pencil and paper to come up with an algorithm to use. Remember the first rule of algorithm, if you can't describe it so it is easily understood by a 6 year old it is not ready to be translated to code.

I have a hint for you. Does it matter which letter doesn't match?
ibreeden and ndc85430 like this post
Reply
#4
I am fascinated by these exercices. Who invents this?
Reading deanhystads post he, probably intentionally, used "crate" and "create".

These can be made identical by adding or removing a letter.
Do the schoolbook rules give a hint on what takes priority ?

Paul
Reply
#5
And, if there is a one character difference, then adding that character to the shorter string makes a match as does removing that same character from the longer string. Hint.
Reply
#6
One algorithm could be (after it is determined, that length difference is 1) : "iterate over strings characters pairwise, if pair characters are not equal, if shorter string character in pair is not equal to next character of longer string then strings are non-identical"
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply
#7
I agree with DPaul that some of these exercises are interesting and I had to do this one.

Agree also with Perfringo about overall approach.

Consider - check to see if the strings are equal. If so, done.
Check to see if the length discrepancy is more than 1. If so, no match, done.
The remaining case is the interesting one. That the strings must be different only by adding a character (can ignore the case of subtracting, as it is the same thing), and that substitution of a character was not an option makes it easier.

Substitution adds a level of complexity...

So, Omid, are you still around?
Reply
#8
Hello,

Guys thank you all. Like you said the tricky part is to add/subtract a letter to make both strings identical. Perhaps a dictionary is helpful. I'm still working on it.
Reply
#9
Pen and paper are programmers best friends (as already suggested by deanhystad) :-). Solution could be easily visualized and become obvious:


Output:
are equal ╭──┴──╮ c | r | a | t | e | ↘ ↘ ↘ c | r | e | a | t | e | ╰─┬─╯ first non equal
'Encountering first unequal character pair all characters in shorter string must equal to next character in longer string'

There are built-in functions in Python to iterate pairwise and to get indices while doing it.
I'm not 'in'-sane. Indeed, I am so far 'out' of sane that you appear a tiny blip on the distant coast of sanity. Bucky Katt, Get Fuzzy

Da Bishop: There's a dead bishop on the landing. I don't know who keeps bringing them in here. ....but society is to blame.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Strings inside other strings - substrings OmarSinno 2 3,622 Oct-06-2017, 09:58 AM
Last Post: gruntfutuk

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020