update trie

keon · keon · commit 2c6190ded1ca · 2016-12-28T23:00:51.000-05:00
diff --git a/README.md b/README.md
@@ -7,15 +7,28 @@ List of Implementations:
 ```
 .
 ├── array
+│   ├── garage.py
 │   ├── house_robber.py
-│   └── longest_increasing_subsequence.py
-├── builtins
-│   ├── dictionary.py
-│   ├── list.py
-│   ├── set.py
-│   └── tuple.py
-├── dynamic_programming
-│   └── max_subarray.py
+│   ├── longest_increasing_subsequence.py
+│   ├── longest_non_repeat.py
+│   ├── plus_one.py
+│   └── wiggle_sort.py
+├── backtrack
+│   ├── anagram.py
+│   ├── combination_sum.py
+│   ├── palindrome_partitioning.py
+│   ├── permute.py
+│   ├── permute_unique.py
+│   ├── subsets.py
+│   └── subsets_unique.py
+├── bfs
+│   └── shortest_distance_from_all_buildings.py
+├── divide-and-conquer
+│   ├── expression-add-operators.py
+│   └── the-skyline-problem.py
+├── dp
+│   ├── max_subarray.py
+│   └── word_break.py
 ├── graph
 │   ├── find_path.py
 │   ├── graph.py
@@ -24,14 +37,23 @@ List of Implementations:
 │   └── hashtable.py
 ├── linkedlist
 │   ├── first_cyclic_node.py
+│   ├── is_palindrome.py
 │   ├── kth_to_last.py
 │   ├── linkedlist.py
 │   └── remove_duplicates.py
 ├── matrix
-│   └── matrix_rotation.txt
-├── output.txt
+│   ├── bomb_enemy.py
+│   ├── matrix_rotation.txt
+│   └── pacific_atlantic.py
+├── out.txt
 ├── queue
-│   └── queue.py
+│   ├── __init__.py
+│   ├── max_sliding_window.py
+│   ├── moving_average.py
+│   ├── queue.py
+│   ├── reconstruct_queue.py
+│   └── zigzagiterator.py
+├── README.md
 ├── search
 │   ├── binary_search.py
 │   ├── count_elem.py
@@ -41,28 +63,49 @@ List of Implementations:
 │   ├── insertion_sort.py
 │   ├── merge_sort.py
 │   ├── quick_sort.py
-│   └── selection_sort.py
+│   ├── selection_sort.py
+│   └── sort_colors.py
 ├── stack
 │   ├── __init__.py
 │   ├── __init__.pyc
+│   ├── longest_abs_path.py
+│   ├── __pycache__
+│   │   ├── __init__.cpython-35.pyc
+│   │   └── stack.cpython-35.pyc
 │   ├── stack.py
 │   └── stack.pyc
 ├── string
+│   ├── decode_string.py
+│   ├── encode_decode.py
 │   ├── license_number.py
+│   ├── missing_ranges.py
+│   ├── rabin_karp.py
 │   ├── reverse_string.py
 │   ├── reverse_vowel.py
-│   └── reverse_words.py
-├── testStack.py
-└── tree
-    ├── bintree2list.py
-    ├── deepest_left.py
-    ├── invert_tree.py
-    ├── longest_abs_path.py
-    ├── max_height.py
-    ├── predecessor.py
-    ├── same_tree.py
-    ├── successor.py
-    ├── tree.py
+│   ├── reverse_words.py
+│   └── word_squares.py
+├── tests
+│   └── test_stack.py
+├── tree
+│   ├── array2bst.py
+│   ├── bintree2list.py
+│   ├── bst_closest_value.py
+│   ├── BSTIterator.py
+│   ├── deepest_left.py
+│   ├── invert_tree.py
+│   ├── is_balanced.py
+│   ├── is_subtree.py
+│   ├── is_symmetric.py
+│   ├── longest_consecutive.py
+│   ├── max_height.py
+│   ├── max_path_sum.py
+│   ├── min_height.py
+│   ├── predecessor.py
+│   ├── same_tree.py
+│   ├── successor.py
+│   └── tree.py
+└── trie
+    ├── add_and_search.py
     └── trie.py
 
 
diff --git a/bfs/shortest_distance_from_all_buildings.py b/bfs/shortest_distance_from_all_buildings.py
@@ -1,8 +1,11 @@
 import collections
 
-## do BFS from each building, and decrement all empty place for every building visit
-## when grid[i][j] == -b_nums, it means that grid[i][j] are already visited from all b_nums
-## and use dist to record distances from b_nums
+"""
+do BFS from each building, and decrement all empty place for every building visit
+when grid[i][j] == -b_nums, it means that grid[i][j] are already visited from all b_nums
+and use dist to record distances from b_nums
+"""
+
 def shortest_distance(grid):
     if not grid or not grid[0]:
         return -1
diff --git a/divide-and-conquer/expression-add-operators.py b/divide-and-conquer/expression-add-operators.py
@@ -0,0 +1,47 @@
+"""
+Given a string that contains only digits 0-9 and a target value,
+return all possibilities to add binary operators (not unary) +, -, or *
+between the digits so they prevuate to the target value.
+
+Examples:
+"123", 6 -> ["1+2+3", "1*2*3"]
+"232", 8 -> ["2*3+2", "2+3*2"]
+"105", 5 -> ["1*0+5","10-5"]
+"00", 0 -> ["0+0", "0-0", "0*0"]
+"3456237490", 9191 -> []
+"""
+
+def add_operator(num, target):
+    """
+    :type num: str
+    :type target: int
+    :rtype: List[str]
+    """
+    res = []
+    if not num: return res
+    helper(res, "", num, target, 0, 0, 0)
+    return res
+
+def helper(res, path, num, target, pos, prev, multed):
+    print(res, path, num, target, pos, prev, multed)
+    if pos == len(num):
+        if (target == prev):
+            res.append(path)
+        return
+    for i in range(pos, len(num)):
+        if i != pos and num[pos] == '0': break
+        cur = int(num[pos:i+1])
+        print(cur)
+        if (pos == 0):
+            helper(res, path + str(cur), num, target, i+1, cur, cur)
+        else:
+            helper(res, path + "+" + str(cur), num, target, i+1, prev + cur, cur)
+            helper(res, path + "-" + str(cur), num, target, i+1, prev - cur, -cur)
+            helper(res, path + "*" + str(cur), num, target, i+1, prev - multed + multed * cur, multed * cur)
+
+
+# "123", 6 -> ["1+2+3", "1*2*3"]
+s = "123"
+target = 6
+print(add_operator(s, target))
+
diff --git a/divide-and-conquer/the-skyline-problem.py b/divide-and-conquer/the-skyline-problem.py
@@ -0,0 +1,66 @@
+"""
+A city's skyline is the outer contour of the silhouette formed by all the buildings
+in that city when viewed from a distance.
+Now suppose you are given the locations and height of all the buildings
+as shown on a cityscape photo (Figure A),
+write a program to output the skyline formed by these buildings collectively (Figure B).
+
+The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi],
+where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively,
+and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0.
+You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
+
+For instance, the dimensions of all buildings in Figure A are recorded as:
+[ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
+
+The output is a list of "key points" (red dots in Figure B) in the format of
+[ [x1,y1], [x2, y2], [x3, y3], ... ]
+that uniquely defines a skyline.
+A key point is the left endpoint of a horizontal line segment. Note that the last key point,
+where the rightmost building ends,
+is merely used to mark the termination of the skyline, and always has zero height.
+Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
+
+For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
+
+Notes:
+
+The number of buildings in any input list is guaranteed to be in the range [0, 10000].
+The input list is already sorted in ascending order by the left x position Li.
+The output list must be sorted by the x position.
+There must be no consecutive horizontal lines of equal height in the output skyline. For instance,
+[...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged
+into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
+
+"""
+
+import heapq
+
+def get_skyline(LRH):
+    """
+    Wortst Time Complexity: O(NlogN)
+    :type buildings: List[List[int]]
+    :rtype: List[List[int]]
+    """
+    skyline, live = [], []
+    i, n = 0, len(LRH)
+    while i < n or live:
+        if not live or i < n and LRH[i][0] <= -live[0][1]:
+            x = LRH[i][0]
+            while i < n and LRH[i][0] == x:
+                heapq.heappush(live, (-LRH[i][2], -LRH[i][1]))
+                i += 1
+        else:
+            x = -live[0][1]
+            while live and -live[0][1] <= x:
+                heapq.heappop(live)
+        height = len(live) and -live[0][0]
+        if not skyline or height != skyline[-1][1]:
+            skyline += [x, height],
+    return skyline
+
+buildings = [ [2, 9, 10], [3, 7, 15], [5, 12, 12], [15, 20, 10], [19, 24, 8] ]
+# [ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ]
+print(get_skyline(buildings))
+
+
diff --git a/hashtable/hashtable.py b/hashtable/hashtable.py
@@ -1,11 +1,12 @@
-# MAP Abstract Data Type
-# Map() Create a new, empty map. It returns an empty map collection.
-# put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.
-# get(key) Given a key, return the value stored in the map or None otherwise.
-# del Delete the key-value pair from the map using a statement of the form del map[key].
-# len() Return the number of key-value pairs stored in the map.
-# in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.
-
+"""
+MAP Abstract Data Type
+Map() Create a new, empty map. It returns an empty map collection.
+put(key,val) Add a new key-value pair to the map. If the key is already in the map then replace the old value with the new value.
+get(key) Given a key, return the value stored in the map or None otherwise.
+del Delete the key-value pair from the map using a statement of the form del map[key].
+len() Return the number of key-value pairs stored in the map.
+in Return True for a statement of the form key in map, if the given key is in the map, False otherwise.
+"""
 class HashTable(object):
     def __init__(self, size = 11):
         self.size = size
diff --git a/trie/add_and_search.py b/trie/add_and_search.py
@@ -1,17 +1,18 @@
-# We are asked to design an efficient data structure
-# that allows us to add and search for words.
-# The search can be a literal word or regular expression
-# containing “.”, where “.” can be any letter.
-
-# Example:
-# addWord(“bad”)
-# addWord(“dad”)
-# addWord(“mad”)
-# search(“pad”) -> false
-# search(“bad”) -> true
-# search(“.ad”) -> true
-# search(“b..”) -> true
+"""
+We are asked to design an efficient data structure
+that allows us to add and search for words.
+The search can be a literal word or regular expression
+containing “.”, where “.” can be any letter.
 
+Example:
+addWord(“bad”)
+addWord(“dad”)
+addWord(“mad”)
+search(“pad”) -> false
+search(“bad”) -> true
+search(“.ad”) -> true
+search(“b..”) -> true
+"""
 
 class TrieNode(object):
     def __init__(self, letter, isTerminal=False):
diff --git a/trie/trie.py b/trie/trie.py
@@ -0,0 +1,37 @@
+"""
+Implement a trie with insert, search, and startsWith methods.
+
+Note:
+You may assume that all inputs are consist of lowercase letters a-z.
+"""
+class TrieNode:
+    def __init__(self):
+        self.children = collections.defaultdict(TrieNode)
+        self.is_word = False
+
+class Trie:
+    def __init__(self):
+        self.root = TrieNode()
+
+    def insert(self, word):
+        current = self.root
+        for letter in word:
+            current = current.children[letter]
+        current.is_word = True
+
+    def search(self, word):
+        current = self.root
+        for letter in word:
+            current = current.children.get(letter)
+            if current is None:
+                return False
+        return current.is_word
+
+    def startsWith(self, prefix):
+        current = self.root
+        for letter in prefix:
+            current = current.children.get(letter)
+            if current is None:
+                return False
+        return True
+
