x[0:1], x[0:2], ..., x[0:len(x)]

class Solution(object):
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
words.sort(key=lambda x: len(x))
tree = {'#': {}}
ans = ''
for word in words:
p = tree
ok = True
for c in word:
if c not in p:
p[c] = {}
ok = ok and '#' in p
p = p[c]
p['#'] = {}
if ok and (len(word) > len(ans) or word < ans):
ans = word
return ans


class Solution(object):
def longestWord(self, words):
"""
:type words: List[str]
:rtype: str
"""
words = set(words)
ans = ''
for word in words:
if len(word) < len(ans):
continue
tmp = word
while tmp in words:
tmp = tmp[:-1]
if tmp:
continue
if len(word) > len(ans) or word < ans:
ans = word
return ans


class Solution(object):
def accountsMerge(self, accounts):
"""
:type accounts: List[List[str]]
:rtype: List[List[str]]
"""
def merge(accounts):
email2name = {}
name2email = {}
for i, account in enumerate(accounts):
name = account[0]
emails = account[1:]
j = i
for email in emails:
if email in email2name:
j = email2name[email]
break
if j not in name2email:
name2email[j] = set()
for email in emails:
email2name[email] = j
ans = []
for k, v in name2email.items():
tmp = [accounts[k][0]]
tmp.extend(list(v))
ans.append(tmp)
return ans
ans = merge(accounts)
while True:
tmp = merge(ans)
if len(tmp) == len(ans):
break
ans = tmp
return [[a[0]]+sorted(a[1:]) for a in ans]


class Solution(object):
"""
:type source: List[str]
:rtype: List[str]
"""
ans = []
multi = False
i = 0
while i < len(source):
cur = source[i]
if multi:
p = cur.find('*/')
if p == -1:
i += 1
continue
cur = cur[p+2:]
if ans:
cur = ans[-1] + cur
ans.pop()
multi = False
p = cur.find('/*')
q = cur.find('//')
if (p == -1 and q >= 0) or (p > q >= 0):
cur = cur[:q]
elif (q == -1 and p >= 0) or (q > p >= 0):
q = cur.find('*/', p+2)
if q == -1:
cur = cur[:p]
multi = True
else:
cur = cur[:p] + cur[q+2:]
source[i] = cur
continue
if len(cur) > 0:
ans.append(cur)
i += 1
return ans


class Solution(object):
def candyCrush(self, board):
"""
:type board: List[List[int]]
:rtype: List[List[int]]
"""
n = len(board)
m = len(board[0])
def eliminate():
ans = set()
for i in xrange(n):
for j in xrange(m):
if board[i][j] == 0:
continue
tmp = []
k = j
while k < m and board[i][j] == board[i][k]:
tmp.append((i, k))
k += 1
if len(tmp) >= 3:
ans |= set(tmp)
tmp = []
k = i
while k < n and board[i][j] == board[k][j]:
tmp.append((k, j))
k += 1
if len(tmp) >= 3:
ans |= set(tmp)
if len(ans) == 0:
return False
for i, j in ans:
board[i][j] = 0
return True

def fall():
for j in xrange(m):
k = n - 1
for i in xrange(n-1, -1, -1):
if board[i][j] != 0:
board[k][j] = board[i][j]
k -= 1
for i in xrange(k, -1, -1):
board[i][j] = 0

while eliminate():
fall()
return board