class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
lst = s.split(' ')
for i in xrange(len(lst)):
if lst[i] == '':
continue
lst[i] = ''.join(reversed(lst[i]))
return ' '.join(lst)


class Solution(object):
def leastBricks(self, wall):
"""
:type wall: List[List[int]]
:rtype: int
"""
cnt = {}
for row in wall:
s = 0
for w in row[:-1]:
s += w
cnt[s] = cnt.get(s, 0) + 1
m = 0
for _, v in cnt.items():
m = max(m, v)
return len(wall) - m


class Solution(object):
def nextGreaterElement(self, n):
"""
:type n: int
:rtype: int
"""
d = []
m = n
while m > 0:
d.append(m % 10)
m /= 10
i = 1
while i < len(d) and d[i] >= d[i-1]:
i += 1
if i == len(d):
return -1
j = i
while j - 1 >= 0 and d[j-1] > d[i]:
j -= 1
d[i], d[j] = d[j], d[i]
d[:i] = sorted(d[:i], reverse=True)
p = 1
ans = 0
for i in d:
ans += i * p
p *= 10
return ans if ans < 2 ** 31 else -1


# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def longestConsecutive(self, root):
"""
:type root: TreeNode
:rtype: int
"""
ans = [0]
def dfs(root):
if not root:
return 0, 0
dec = inc = 1
if root.left:
d, i = dfs(root.left)
if root.val == root.left.val + 1:
dec = d + 1
elif root.val == root.left.val - 1:
inc = i + 1

if root.right:
d, i = dfs(root.right)
if root.val == root.right.val + 1:
dec = max(dec, d+1)
elif root.val == root.right.val - 1:
inc = max(inc, i+1)

ans[0] = max(ans[0], dec + inc - 1)
return dec, inc

dfs(root)
return ans[0]