no message

Chris Wu · Chris Wu · commit 46e715f3ad44 · 2019-04-10T22:12:44.000+08:00
diff --git a/group-anagrams.py b/group-anagrams.py
@@ -1,14 +1,7 @@
 #https://leetcode.com/problems/group-anagrams/
 class Solution(object):
     def groupAnagrams(self, strs):
-        dic = collections.defaultdict(list)
-        
-        for string in strs:
-            string_count = [0]*26
-            a = ord('a')
-            for char in string:
-                string_count[ord(char)-a] += 1
-                
-            dic[tuple(string_count)].append(string)
-        
-        return dic.values()
+        anagrams = collections.defaultdict(list)
+        for s in strs:
+            anagrams[''.join(sorted(s))].append(s)
+        return anagrams.values()
diff --git a/jump-game.py b/jump-game.py
@@ -0,0 +1,20 @@
+"""
+Let's reverse engineer the process.
+Imagine you are standing at the last index i
+index i-1 will need the value>=1 to go to i (step_need=1)
+index i-2 will need the value>=2 to go to i (step_need=2)
+...
+
+At a certain index x, the value>=step_need
+This means that, from x, we can go to i no problem.
+Now we are standing at x and reset step_need to 0.
+See if we can repeat the process until we reach the first index.
+"""
+class Solution(object):
+    def canJump(self, nums):
+        step_need = 0
+        for num in reversed(nums[:-1]):
+            step_need+=1
+            if num>=step_need:
+                step_need = 0
+        return step_need==0
diff --git a/serialize-and-deserialize-bst.py b/serialize-and-deserialize-bst.py
@@ -0,0 +1,45 @@
+"""
+perform BFS to traverse the whole tree
+after we add the entire level to the string, then we go to the next level
+
+by doing this, we can always convert the serialized tree back
+because when you build the tree back
+the order doesn't matter as long as you insert each parent before child
+"""
+
+from collections import deque
+class Codec:
+    def serialize(self, root):
+        if root==None: return ''
+        s=''
+        queue = deque([root])
+        while queue:
+            node = queue.popleft()
+            s+=str(node.val)+','
+            if node.left: queue.append(node.left)
+            if node.right: queue.append(node.right)
+        return s[:-1]
+            
+    def deserialize(self, data):
+        if data==None or data=='': return None
+        data = map(int, data.split(','))
+        root = TreeNode(data[0])
+        for i in xrange(1, len(data)):
+            val = data[i]
+            node = root
+            while True:
+            	if val==node.val:
+            		print('Input Error')
+                elif val>node.val:
+                    if node.right==None:
+                        node.right = TreeNode(val)
+                        break
+                    else:
+                        node = node.right
+                else:
+                    if node.left==None:
+                        node.left = TreeNode(val)
+                        break
+                    else:
+                        node = node.left
+        return root
diff --git a/valid-parentheses.py b/valid-parentheses.py
@@ -13,3 +13,26 @@ def isValid(self, s):
             return False
 
 
+class Solution(object):
+    def isValid(self, s):
+        stack = []
+        for c in s:
+            if c=='(' or c=='[' or c=='{':
+                stack.append(c)
+            elif c==')':
+                if stack and stack[-1]=='(':
+                    stack.pop()
+                else:
+                    stack.append(c)
+            elif c==']':
+                if stack and stack[-1]=='[':
+                    stack.pop()
+                else:
+                    stack.append(c)
+            elif c=='}':
+                if stack and stack[-1]=='{':
+                    stack.pop()
+                else:
+                    stack.append(c)
+        return len(stack)==0
+        
