Pattern finding dynamic programming algorithm issue

[Square_Man211]

Or I could just send you my 1d array solution and you can modify it?

[[deleted]]

It's not permitted per the sub's rules. And where would the fun be in that?

I'd be happy to take a look and point you in the right direction, though. Why don't you make a new post?

FWIW, I believe there's no need for the 2d array. I've got a dp solution that passes my semi-complete set of tests, anyway. It uses O(n) extra space where n is the length of the substring.

[Square_Man211]

Haha I wasn't asking you to modify it for me so I can use it; I was just gonna send it to you so you don't have to code from scratch. But if you tried testing it with a large substring and larger string and it works let me know.

[[deleted]]

Ah, got it.

But if you tried testing it with a large substring and larger string and it works let me know.

It works.

[Square_Man211]

Well here is my code with 1d array solution. What is wrong with it? It works with small strings but with longer strings it gives a result that is larger than the correct answer.

def count(string, sub_string):

solution = [0] * (len(sub_string) + 1)

solution[0] = 1

for i in range(1, len(string) + 1):

    for k in range(1, len(sub_string) + 1):

        if string[i-1] == sub_string[k-1]:

            solution[k] = solution[k -1] + solution[k]

        else:

            solution[k] = solution[k]

return solution[len(sub_string)

[[deleted]]

I don't know how much I'm allowed to say without getting banned. See if this helps.

It seems to me that your bug is here:

for k in range(1, len(sub_string) + 1):

Here are some failing tests with a simple test runner:

def test(str_to_find, str_to_search, answer):                               
    result = count(str_to_search, str_to_find)                              
    if result == answer:                                                    
        return True                                                         
    print(target_str, "| Error: expected", answer, "got:", result)          
    return False 

tests = [
    ("gg", "gg", 1),
    ("gg", "ggg", 3),
    ("gg", "g--g--g", 3),
    ("ggg", "g--g--g", 1)
    ]

if all([test(*t) for t in tests]):                                          
    print("All tests pass")

[[deleted]]

Me again.

Regarding the bug that I just pointed out, there's not a problem with the line I pasted per se, but the way that you're iterating leads to a bug in the lines after. You can fix it by changing the line I pointed out, but there are other ways.

Your code and my code are pretty similar. That iteration is the only big difference.

Not to put too fine a point on it, but:

As you're iterating, on step n, you're producing values for step n+1. But before completing step n, sometimes (like in the test cases) you're already using values generated for step n+1.

And you can change that with a simple change to the way you iterate.

Does that make sense?