You definitely want to take a dynamic programming approach to this problem, as explained by Justin, if only to make the code more readable. I've included a solution based on this approach at the end.
I found the code fairly difficult to read due to the way it is structured. In its present form it wont be very re-usable, due to the use of global variables and the lack of any overall encapsulation.
For example, the following section, which finds all palindromic substrings, should be encapsulated in a function. And, it would be best for
find_partitions to somehow make its own call to this function, rather than to rely on a result stored in a global variable.
for start in range (len(word)):
while end < len(word) + 1:
if word[start:end] == word[start:end][::-1]:
I wasn't able to determine the correctness of the program from inspection, but it appears to produce correct answers, except for inputs that are already palindromes (i.e. require zero cuts), in which case it throws an error.
Also, there's a subtle problem with way you've specified the default value for
Again, I wasn't able to fully analyse the efficiency by inspection. However it seems to perform about as well as my solution.
On naming variables:
- I think
paritions is a spelling mistake. Did you mean
- Some of the names could be made more descriptive, such as
The use of whitespace is a little bit inconsistent. I would make the following changes based on the python style guide:
find_paritions(to_explore, word, running)
complete_paths = 
parition_count =0 ->
parition_count = 0
range (len(word)) ->
end = start + 1
end +=1 ->
end += 1
find_paritions (list_zeroes,word) ->
It wasn't clear to me that
running = running + [item] served the role of duplicating running before appending
item, so I ended up correcting it to
running.append(item) which of course broke the code. Maybe a comment here would be worthwhile, or this statement could be written in such a way that it draws attention to the duplication (e.g.
new_running = running + [item], then you wouldn't have to use
pop on each successive iteration).
For comparison, here is a solution that uses dynamic programming:
def least_palin_cuts(string, memo=None):
"""Return the minimum number of cuts required to break string into
>>> least_palin_cuts('ababbbabbababa') # a|babbbab|b|ababa
>>> least_palin_cuts('partytrapb') # partytrap|b
>>> least_palin_cuts('kayak') # kayak (no cuts needed)
if memo is None:
memo = dict()
if string not in memo:
memo[string] = 0
memo[string] = min(
least_palin_cuts(left, memo) + 1 + least_palin_cuts(right, memo)
for (left, right) in splits(string)
"""Return True if string is a palindrome, else False."""
return all(c1 == c2 for (c1, c2) in zip(string, reversed(string)))
"""Generate each way of splitting string into two non-empty substrings.
[('a', 'bc'), ('ab', 'c')]
for i in range(1, len(string)):
yield (string[:i], string[i:])