# Accepted Python solution, DFS, 265 ms

• 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()
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

``````

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