Accepted Python solution, DFS, 265 ms


  • 0
    M

    Simple DFS where state is water level in bucket y with bucket x being empty. Only four transitions are possible (check in the code).

    class Solution(object):
        def canMeasureWater(self, x, y, z):
            if x == z or y == z:
                return True
            if (x + y) < z:
                return False
            if (x == 0 or y == 0) and z > 0:
                return False
            if z == 0:
                return True
    
            # Make y to be larger bucket
            x, y = min(x, y), max(x, y)
            
            states = [0]
            visited = set([])
            while states:
                # State is a water level in y, while x is empty.
                state = states.pop()
                visited.add(state)
                if state == z or (x + state) == z:
                    return True
                # Fill x full, pour water from x to y.
                s = state + x
                if s <= y and s not in visited:
                    states.append(s)
                # Pour water from y to x, empty x.
                s = state - x
                if s > 0 and s not in visited:
                    states.append(s)
                # Pour water from y to x, fill y full, pour from y to x, empty x.
                s = y - (x - state)
                if s > 0 and s <= y and s not in visited:
                    states.append(s)
                # Fill x, pour from x to y, empty y, pour from x to y.
                s = x - (y - state)
                if s > 0 and s <= y and s not in visited:
                    states.append(s)
            return False
    
    

Log in to reply
 

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