class Solution(object):
def floodFill(self, image, sr, sc, newColor):
"""
:type image: List[List[int]]
:type sr: int
:type sc: int
:type newColor: int
:rtype: List[List[int]]
"""
visited = set()
n = len(image)
m = len(image[0])
color = image[sr][sc]

def dfs(r, c):
image[r][c] = newColor
for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
x, y = r+dr, c+dc
if x < 0 or y < 0 or x >= n or y >= m or image[x][y] != color:
continue
if (x, y) in visited:
continue
dfs(x, y)

dfs(sr, sc)
return image


class Solution(object):
def areSentencesSimilar(self, words1, words2, pairs):
"""
:type words1: List[str]
:type words2: List[str]
:type pairs: List[List[str]]
:rtype: bool
"""
if len(words1) != len(words2):
return False
m = {}
for a, b in pairs:
if a not in m:
m[a] = set([a])
if b not in m:
m[b] = set([b])
for a, b in zip(words1, words2):
if a not in m:
if a != b:
return False
else:
if b not in m[a]:
return False
return True


class Solution(object):
def asteroidCollision(self, asteroids):
"""
:type asteroids: List[int]
:rtype: List[int]
"""
ans = []
for a in asteroids:
if not ans or a > 0 or ans[-1]*a > 0:
ans.append(a)
continue
while ans and ans[-1] > 0 and ans[-1]+a < 0:
ans.pop()
if not ans or ans[-1] < 0:
ans.append(a)
continue
if ans[-1]+a == 0:
ans.pop()
return ans


split是将表达式ex分成若干块，每一块都是合法的子表达式。

get首先假设输入参数v是一个变量，直接尝试转化成整数或者从局部变量集合ls或者全局变量gs中获得。如果上述方法无法获得v的值，说明v是一个表达式而不是变量，所以对v调用lisp函数。

lisp的输入参数ex表示一个表达式，gs表示全局变量列表。首先调用split函数将ex分解，然后按照let, addmult分类讨论。

class Solution(object):
def evaluate(self, expression):
"""
:type expression: str
:rtype: int
"""
def split(ex):
el = []
cur = ''
p = 0
s = 5
if ex.startswith('(mult'):
s = 6
for ch in ex[s:-1]:
if ch == '(':
p += 1
elif ch == ')':
p -= 1
elif ch == ' ':
if p == 0:
el.append(cur)
cur = ''
continue
cur += ch
el.append(cur)
return el

def get(v, ls, gs):
try:
return int(v)
except:
if v in ls:
return ls[v]
for g in gs[::-1]:
if v in g:
return g[v]
gs.append(ls)
ans = lisp(v, gs)
gs.pop()
return ans

def lisp(ex, gs):
ls = {}
el = split(ex)

if ex.startswith('(let'):
for i in range(0, len(el)-1, 2):
ls[el[i]] = get(el[i+1], ls, gs)
return get(el[-1], ls, gs)
else:
first = get(el[0], ls, gs)
second = get(el[1], ls, gs)