Python BFS search with memoization


  • 0
    D

    I got asked this question in a real life interview, I thought of just doing BFS to search for the solution. Turns out the BFS with memoization is pretty easy to code and performs well enough.

    from collections import deque
    
    class Solution(object):
      def minCut(self, s):
        """
        :type s: str
        :rtype: int
        """
        def is_palin(t):
          return t == t[::-1]
      
        q = deque([(len(s), 0)])  # in the form (idx to cut, # of cuts)
        # keep track of which cut we are already exploring
        seen = set()
        while q:
          pre_idx, cuts = q.popleft() . # pop left to do BFS
          pre = s[:pre_idx]
          if is_palin(pre):
            return cuts
          
          for i in xrange(1, len(pre)):
            if i in seen:  # another search already cut here
              continue
            post = pre[i:]  # invariant is that everything in post is already palindrome
            if not is_palin(post):
              # if we cut at current index i, the postfix doesn't satisfy our invariant
              continue
            # found a place to cut where substring s[i:] can be partition into palindromes
            q.append((i, cuts+1))
            seen.add(i) # memoize where we are already cutting
        
        return len(s) - 1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.