Palindromic partitions solution

Question

Task

Find the smallest number of cuts required to break a string into a set of valid palindromes. For example:

• ababbbabbababa becomes a|babbbab|b|ababa (cuts = 3)
• partytrapb becomes partytrap|b (cuts = 1)

Note: all strings of length 1 are palindromes as a single character reads the same forward and backward

import re 
def find_paritions(lst, word, running=[]):
 for (index,item) in enumerate(lst):
 if index > 0:
 running.pop()
 running = running + [item]
 if item[1] == len(word):
 complete_paths.append(running)
 return 
 to_explore = []
 end = item[1]
 for item_next in list_parition_index:
 if item_next[0] == end:
 to_explore.append(item_next)
 if len(to_explore) == 0: 
 return 
 find_paritions(to_explore,word,running)
 return complete_paths
complete_paths=[] 
word = "ababbbabbababa"
start = 0
end = 1
parition_count =0
list_parition_index = []
for start in range (len(word)):
 end=start+1
 while end < len(word) + 1:
 if word[start:end] == word[start:end][::-1]:
 list_parition_index.append([start,end])
 end +=1
 else:
 end +=1
list_zeroes = [x for x in list_parition_index if x[0] == 0]
x = find_paritions (list_zeroes,word)
print(f"The total number of divisions required is {len(min(x,key=len))-1}")
print(min(x,key=len))

Answer 1

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.

---

Structure

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)):
 end=start+1
 while end < len(word) + 1:
 if word[start:end] == word[start:end][::-1]:
 list_parition_index.append([start,end])
 end +=1
 else:
 end +=1

Correctness

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 running.

Efficiency

Again, I wasn't able to fully analyse the efficiency by inspection. However it seems to perform about as well as my solution.

Style

• Redundancy:
  • You import re but don't use it
  • Initialising start and end isn't necessary
  • This section

    if ...:
     ...
     end +=1
    else:
     end +=1
    

    could be replaced with

    if ...:
     ...
    end +=1
    

• On naming variables:

  • I think paritions is a spelling mistake. Did you mean partitions?
  • Some of the names could be made more descriptive, such as lst, item, item_next, and running.

• The use of whitespace is a little bit inconsistent. I would make the following changes based on the python style guide:

  • (index,item) -> (index, item)
  • find_paritions(to_explore,word,running) -> find_paritions(to_explore, word, running)
  • complete_paths=[] -> complete_paths = []
  • parition_count =0 -> parition_count = 0
  • range (len(word)) -> range(len(word))
  • [start,end] -> [start, end]
  • end=start+1 -> end = start + 1
  • end +=1 -> end += 1
  • find_paritions (list_zeroes,word) -> find_paritions(list_zeroes, word)
  • min(x,key=len) -> min(x, key=len)

• 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 
 palindromic substrings.
 >>> least_palin_cuts('ababbbabbababa') # a|babbbab|b|ababa
 3
 >>> least_palin_cuts('partytrapb') # partytrap|b
 1
 >>> least_palin_cuts('kayak') # kayak (no cuts needed)
 0
 """
 if memo is None:
 memo = dict()
 if string not in memo:
 if is_palindrome(string):
 memo[string] = 0
 else:
 memo[string] = min(
 least_palin_cuts(left, memo) + 1 + least_palin_cuts(right, memo)
 for (left, right) in splits(string)
 )
 return memo[string]
def is_palindrome(string):
 """Return True if string is a palindrome, else False."""
 return all(c1 == c2 for (c1, c2) in zip(string, reversed(string)))
def splits(string):
 """Generate each way of splitting string into two non-empty substrings.
 >>> list(splits('abc'))
 [('a', 'bc'), ('ab', 'c')]
 """
 for i in range(1, len(string)):
 yield (string[:i], string[i:])

• QuantumChris: For is_palindrome, why not just return string == string[::-1]?
• user2846495: My thought was that string == string[::-1] might not terminate early if, say, string[0] != string[-1], whereas all will stop at the first non-true value. It does seem to make a difference, but only for very large strings: with s = 'b' + 'a' * 1_000_000, I got 1.1 ms ± 4.53 µs per loop for %timeit s == s[::-1] and 958 ns ± 4.74 ns per loop for %timeit all(...).