Python BFS search with memoization

  • 0

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