Question

Problem Set 3 Problem 4 bug question:

See my code here: http://pastebin.com/hd5jHVVr

This code fails the test case test subStringMatchExactlyOneSub(target1,key10) because it does not return the last location 20 when subStringMatchOneSub(target1,key10) is called.

I corrected this by changing the for loop on line 53 to the following:

for i in range(0,len(target)+1):

Can anyone explain why the +1 is necessary when len(target) is equal to the length of the string and should iterate through all characters?

Answer 1

So, good question and, thankfully, the answer is just that this is a strange syntactical idiosyncrasy with Python... When you specify a range in Python, it starts at the beginning - in this case 0 - and then goes all the way **up-to-but-not-including** the final number. That's it. So, for ex., if you were searching through the integers 0 and 4,

for i in range(0, 4)

would do

i=0, i=1, i=2 and i=3,

but

for i in range(0,5)

would also do i=4, but **not** i=5.

Mathematically, for i in range(0,4) searches the set of integers [0,4) and for i in range(0,5) searches the set of integers [0,4] (which is [0,5) too...)

Good question!

Answer 2

AlexanderR, I tried your code. I guess this '+1' just happens to solve it. My solution works just fine and it's a little bit more efficient.
http://codepad.org/RM8VLrbu

Answer 3

@swdalb So, the bug was coming from the range() function. Thanks, I was focusing in on the len() function. Lesson learned, calling the function range(0,len(string)) for any reason can cause some bugs because the loop will iterate one cycle to few.

@oogs Agreed, more efficient than pure enumeration

Answer 4

Also, thanks for the responses!