@StefanPochmann
I found there is little difference in Python for these two solution.
The first 1600ms+ and the second 1500ms+
Jianghan Li
@lee215
Posts made by lee215

RE: 67 lines, 2 ways

RE: Python concise solution, O(N) and 1 line
@motal
heap takes O(log3) = O(1) in case of both push and pop. 
RE: Python, Simple with Explanation
@sha256pki
It will remove all keys with value zero and negative. 
RE: One suggestion for all solutions
@StefanPochmann
Added regex :)
Well, I have to say, I am not good enough at this part. 
One suggestion for all solutions
I suggest to do this treatment, before go directly DP.
Shorten the original string, like reduce
aaabbb
toab
.The same consecutive characters won't change the result and this really help improve the efficiency.
Besides, in python, it takes only 1 line to do it:
s = ''.join(a for a, b in zip(s, '#' + s) if a != b)
or use regex
s = re.sub(r'(.)\1*', r'\1', s)
Edited after stefan's suggestion.

RE: Python concise solution, O(N) and 1 line
@motal
It is O(logN) for insert. In my case it takes O(1) to keep nlargest and O(N) to parse all numbers. 
Python useful solution
This is not a very efficace solution. Because it use
eval
function.
In fact I wrote a function to help me find all solutions for 24 game.
Efficacy was not that important. Then I met this problem I just modified my original solution to return justTrue
orFalse
def judgePoint24(self, nums): def f(s1, s2): res = [] for a in s1: for b in s2: res.append('(' + a + '+' + b + ')') res.append('(' + a + '' + b + ')') res.append('(' + b + '' + a + ')') res.append(a + '*' + b) res.append(a + '/' + b) res.append(b + '/' + a) return res nums = [str(float(i)) for i in nums] for c in itertools.permutations(nums): eq1 = f(f(f([c[0]], [c[1]]), [c[2]]), [c[3]]) eq2 = f(f([c[0]], [c[1]]), f([c[2]], [c[3]])) for eq in eq1 + eq2: try: if 23.9 <= eval(eq) <= 24.1: print eq.replace(".0", "") return True except: pass return False

Python easy understand solution
The number of open parenthesis is in a range
[cmin, cmax]
cmax
counts the maximum open parenthesis, which means the maximum number of unbalanced '(' that COULD be paired.
cmin
counts the minimum open parenthesis, which means the number of unbalanced '(' that MUST be paired.The string is valid for 2 condition:
cmax
will never be negative.cmin
is 0 at the end.
def checkValidString(self, s): cmin = cmax = 0 for i in s: if i == '(': cmax += 1 cmin += 1 if i == ')': cmax = 1 cmin = max(cmin  1, 0) if i == '*': cmax += 1 cmin = max(cmin  1, 0) if cmax < 0: return False return cmin == 0
or shorter:
def checkValidString(self, s): cmin = cmax = 0 for i in s: cmax = cmax1 if i==")" else cmax+1 cmin = cmin+1 if i=='(' else max(cmin  1, 0) if cmax < 0: return False return cmin == 0
Edited after vonzcy's suggestion.

Python easy and concise 3 lines solution
class MapSum(object): def __init__(self): self.d = {} def insert(self, key, val): self.d[key] = val def sum(self, prefix): return sum(self.d[i] for i in self.d if i.startswith(prefix))
Edited after Stefan's suggestion.