class Solution(object):
def checkValidString(self, s):
"""
:type s: str
:rtype: bool
"""
m = len(s)
if m == 0: return True
f = [set() for i in xrange(m + 1)]
f[0].add(0)
for i in xrange(1, m + 1):
for v in f[i1]:
if s[i1] == '(':
f[i].add(v + 1)
elif s[i1] == ')':
if v  1 >= 0:
f[i].add(v1)
else:
f[i].add(v + 1)
if v  1 >= 0:
f[i].add(v  1)
f[i].add(v)
return 0 in f[m]
Andrinux
@Andrinux
Posts made by Andrinux

Simple Python DP solution using Counter

RE: Very simple Python BFS, But Why TLE??
@yuchengtang94
I tried to set the visited flag before adding it into the queue, i still get TLE... 
Python, Two Iterators, O(logN + K) time
class Iterator(): def __init__(self, root, target, flag): self.stk = [] self.cur = None self.dir = flag p = root if flag: while p: if abs(p.val  target) < 0.001: self.cur = p break elif p.val < target: p = p.right else: self.stk.append(p) p = p.left else: while p: if abs(p.val  target) < 0.001 or p.val > target: p = p.left else: self.stk.append(p) p = p.right def hasNext(self): while self.cur: self.stk.append(self.cur) self.cur = self.cur.left if self.dir else self.cur.right return len(self.stk) > 0 or self.cur def next(self): if not self.hasNext(): return None self.cur = self.stk.pop() value = self.cur.val self.cur = self.cur.right if self.dir else self.cur.left return value class Solution(object): def closestKValues(self, root, target, k): """ :type root: TreeNode :type target: float :type k: int :rtype: List[int] """ if root is None: return [] fwd = Iterator(root, target, True) bkd = Iterator(root, target, False) A, B = [], [] for i in xrange(k): if fwd.hasNext(): B.append(fwd.next()) if bkd.hasNext(): A.append(bkd.next()) i, j = 0, 0 ret = collections.deque() while len(ret) < k: v1 = A[i] if i < len(A) else sys.maxint v2 = B[j] if j < len(B) else sys.maxint if abs(v1  target) < abs(v2  target): ret.appendleft(v1) i += 1 else: ret.append(v2) j += 1 return list(ret)

Very simple Python BFS, But Why TLE??
I thought it is a straightforward BFS search, so I write it like the following.
Actually, I have the same question withNumber of Island
problem:
https://discuss.leetcode.com/topic/88586/whypythonbfsgettimeexceederrorimport collections class Solution(object): def cutOffTree(self, G): """ :type forest: List[List[int]] :rtype: int """ if not G or not G[0]: return 1 m, n = len(G), len(G[0]) trees = [] for i in xrange(m): for j in xrange(n): if G[i][j] > 1: trees.append((G[i][j], i, j)) trees = sorted(trees) count = 0 cx, cy = 0, 0 for h, x, y in trees: step = self.BFS(G, cx, cy, x, y) if step == 1: return 1 else: count += step G[x][y] = 1 cx, cy = x, y return count def BFS(self, G, cx, cy, tx, ty): m, n = len(G), len(G[0]) visited = [[False for j in xrange(n)] for i in xrange(m)] Q = collections.deque() step = 1 Q.append((cx, cy)) while len(Q) > 0: size = len(Q) step += 1 for i in xrange(size): x, y = Q.popleft() visited[x][y] = True if x == tx and y == ty: return step for nx, ny in [(x + 1, y), (x  1, y), (x, y1), (x, y + 1)]: if nx < 0 or nx >= m or ny < 0 or ny >= n or G[nx][ny] == 0 or visited[nx][ny]: continue Q.append((nx, ny)) return 1

RE: Simple Python BFS, without set()
@vonzcy
python's integer could be extended automatically. There is not ahard
integer limit like C++/Java. And here,sys.maxint
is9223372036854775807
. It is large enough for almost all applications. 
Simple Python BFS, without set()
class Solution(object): def findSecondMinimumValue(self, root): """ :type root: TreeNode :rtype: int """ if root is None: return 1 Q = collections.deque() Q.append(root) first, ret = root.val, sys.maxint while Q: node = Q.popleft() if node.val > first: ret = min(ret, node.val) if node.left: Q.append(node.left) if node.right: Q.append(node.right) return ret if ret != sys.maxint else 1

RE: Python Solution using PriorityQueue
@sha256pki
I was using a list to store the lengths at beginning, until I get this case failed:
[5,6,7,7,8,8,9,10,11,12]
When we work on the first8
, there are two runs stored in dict,567
,7
. Intuitively speaking, we should append8
with the shorter one. So a simple list cannot pick up the shortest one directly.Abot the time complexity, it looks not very straightforward. It should be like this form
O(nlogk)
,k
is the average length of each heap. so the valuek
depends on the input data pattern. 
RE: Python Solution using PriorityQueue
@sth4nothing
Right, I was using a lot of C++ before. So in Python, I am always using PriorityQueue instead of heapq..
I spend quite a long time to try different methods to optimize before I found heapq works. [Facepalm] 
RE: Python Solution using PriorityQueue
use
collections.PriorityQueue()
will cause TLE. (It looks collections.PriorityQueue is not very efficient )
So I use heapq instead. 
Python Solution using PriorityQueue
I am using a kind of greedy method.
runs
build a map betweentail number
and the currentrun length
. For example, for a consecutive seq3,4,5
, thekey(tail number)
is5
and length is3
.The problem is there might be multiple sub seqs which all end with the same number, but have different length. like we have another subseq
4,5
. So there are two entries in the value part of5
:runs: {5: [3,2]}
so, when we met a new number
6
, we want to merge it into existing subseqs. Which one should we use? Intuitively, if we pick up the shorter one and append the new number into that, we are more likely to make sure all the seqs are longer than3
. So I use a PriorityQueue to store these length.import heapq class Solution(object): def isPossible(self, A): runs = {} # end > [lengths] for v in A: if v  1 not in runs: if v not in runs: runs[v] = [1] else: heapq.heappush(runs[v], 1) else: length = heapq.heappop(runs[v1]) + 1 if len(runs[v1]) == 0: del runs[v1] if v not in runs: runs[v] = [] heapq.heappush(runs[v], length) for v, arr in runs.items(): if len(arr) > 0 and min(arr) < 3: return False return True