class Solution(object):
def canPlaceFlowers(self, flowerbed, n):
"""
:type flowerbed: List[int]
:type n: int
:rtype: bool
"""
cnt = 0
for i in xrange(len(flowerbed)):
if flowerbed[i] == 1:
continue
if i-1>=0 and flowerbed[i-1]==1:
continue
if i+1<len(flowerbed) and flowerbed[i+1]==1:
continue
flowerbed[i] = 1
cnt += 1
return cnt>=n


# 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 tree2str(self, t):
"""
:type t: TreeNode
:rtype: str
"""
if not t:
return ''
left = self.tree2str(t.left)
right = self.tree2str(t.right)
if left and right:
return '{}({})({})'.format(t.val, left, right)
if left:
return '{}({})'.format(t.val, left)
if right:
return '{}()({})'.format(t.val, right)
return '{}'.format(t.val)


class Solution(object):
def findDuplicate(self, paths):
"""
:type paths: List[str]
:rtype: List[List[str]]
"""
files = {}
for path in paths:
fs = path.split(' ')
for name in fs[1:]:
p = name.find('(')
fn = name[:p]
c = name[p+1:-1]
if c not in files:
files[c] = []
files[c].append('{}/{}'.format(fs[0], fn))
ans = []
for v in files.values():
if len(v) >= 2:
ans.append(v)
return ans


class Solution(object):
def isValid(self, code):
"""
:type code: str
:rtype: bool
"""
if not self.is_enclosed(code):
return False
try:
code = self.remove_cdata(code)
except:
return False
tags = []
b = code.find('<')
while b!=-1:
e = b+1
while e<len(code) and code[e]!='>':
e += 1
if e==len(code):
return False
tag = code[b+1:e]
if len(tag)==0 or tag=='/':
return False
if tag[0]!='/':
if len(tag) > 9 or not all('A'<=c<='Z' for c in tag):
return False
tags.append(tag)
else:
tag = tag[1:]
if len(tag) > 9 or not all('A'<=c<='Z' for c in tag):
return False
if not tags or tags[-1]!=tag:
return False
tags.pop()
b = code.find('<', e+1)
return not tags

def is_enclosed(self, code):
if not code or code[0] != '<':
return False
e = code.find('>')
if e==-1:
return False
tag = code[1:e]
if len(tag) < 1 or len(tag) > 9 or not all('A'<=c<='Z' for c in tag):
return False
return code.endswith('</{}>'.format(tag))

def remove_cdata(self, code):
b = code.find('<![CDATA[')
while b!=-1:
e = code.find(']]>', b)
if e==-1:
raise 'error'
code = code[:b]+code[e+3:]
b = code.find('<![CDATA[')
return code