3
\$\begingroup\$

This code is meant to find the length of the largest substring within a string that starts and ends with a given non-empty substring. Here are some examples:

strDist("catcowcat", "cat") → 9
strDist("catcowcat", "cow") → 3
strDist("cccatcowcatxx", "cat") → 9

This is based off this question.

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

def strDist(string, sub):
    if len(string) < len(sub):
        return 0
    elif string[0:len(sub)] == sub and string[-len(sub):] == sub:
        return len(string)
    elif string[0:len(sub)] == sub and string[-len(sub):] != sub:
        return strDist(string[:-1], sub)
    elif string[0:len(sub)] != sub and string[-len(sub):] == sub:
        return strDist(string[1:], sub)
    elif string[0:len(sub)] != sub and string[-len(sub):] != sub:
        return strDist(string[1:-1], sub)

While the original question said that this should be done recursively, I would also be interested to see if there are any nice non-recursive ways of doing this. Also, let me know if a recursive or non-recursive approach would be preferable in an interview (assuming the question wasn't restricted to doing it recursively).

I think this algorithm is O(n) time complexity but O(n^2) space complexity. Correct me if I'm wrong. Also, any suggestions about how to improve complexities are welcome.

\$\endgroup\$
3
\$\begingroup\$

You should use str.startswith and str.endswith and avoid reinventing them with list slicing.

The conditions can be simplified: if the string does not start with the substring remove the first char if it does not end with the substring remove the last.

Space complexity can be reduced by passing indexes to the recursive invocations instead of copies of the string.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. I never heard about str.startswith and str.endswith until now. I does make things clearer. And the simplified conditions sound much nicer. I also like the suggestion of passing indexes instead of the string. That should help with the space complexity. Would it just become O(n) then? \$\endgroup\$ – cycloidistic Nov 26 '16 at 2:03
  • \$\begingroup\$ @cycloidistic Yes it would become O(N) \$\endgroup\$ – Caridorc Nov 26 '16 at 14:30
1
\$\begingroup\$

Right now you are checking the same conditions multiple times. It would be better to use nested ifs.

I also used here str.startswith and str.endswith, but not passing the indices, like @Caridorc suggested in his answer, for simplicity.

def strDist(string, sub): 
    if len(string) < len(sub): 
        return 0 
    elif string.startswith(sub):
        if string.endswith(sub):
            return len(string)
        else:
            return strDist(string[:-1], sub) 
    else:
        if string.endswith(sub):
             return strDist(string[1:], sub)
        else:
            return strDist(string[1:-1], sub)

This way each condition will only be checked once.

\$\endgroup\$
  • \$\begingroup\$ Nesting the if statements does make it nicer. Thanks for the suggestion. \$\endgroup\$ – cycloidistic Nov 26 '16 at 2:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.