add pattern match

keon · keon · commit 708c190e886e · 2017-02-28T03:47:14.000-05:00
diff --git a/array/garage.py b/array/garage.py
@@ -40,10 +40,10 @@ def garage(beg, end):
         if i == len(beg):
             i = 0
     return moves
-                
-                
-initial = [1,2,3,0,4]
-final = [0,3,2,1,4]
-print("initial:", initial)
-print("final:", final)
-print(garage(initial, final))
+
+if __name__ == "__main__":
+    initial = [1,2,3,0,4]
+    final = [0,3,2,1,4]
+    print("initial:", initial)
+    print("final:", final)
+    print(garage(initial, final))
diff --git a/backtrack/pattern_match.py b/backtrack/pattern_match.py
@@ -0,0 +1,52 @@
+"""
+Given a pattern and a string str,
+find if str follows the same pattern.
+
+Here follow means a full match, such that there is a bijection between
+a letter in pattern and a non-empty substring in str.
+
+Examples:
+pattern = "abab", str = "redblueredblue" should return true.
+pattern = "aaaa", str = "asdasdasdasd" should return true.
+pattern = "aabb", str = "xyzabcxzyabc" should return false.
+Notes:
+You may assume both pattern and str contains only lowercase letters.
+"""
+
+
+def pattern_match(pattern, string):
+    """
+    :type pattern: str
+    :type string: str
+    :rtype: bool
+    """
+    return DFS(pattern, string, {})
+
+
+def DFS(pattern, string, dic):
+    print(dic)
+    if len(pattern) == 0 and len(string) > 0:
+        return False
+    if len(pattern) == len(string) == 0:
+        return True
+    for end in range(1, len(string)-len(pattern)+2):
+        if pattern[0] not in dic and string[:end] not in dic.values():
+            dic[pattern[0]] = string[:end]
+            if DFS(pattern[1:], string[end:], dic):
+                return True
+            del dic[pattern[0]]
+        elif pattern[0] in dic and dic[pattern[0]] == string[:end]:
+            if DFS(pattern[1:], string[end:], dic):
+                return True
+    return False
+
+if __name__ == "__main__":
+    pattern1 = "abab"
+    string1 = "redblueredblue"
+    pattern2 = "aaaa"
+    string2 = "asdasdasdasd"
+    pattern3 = "aabb"
+    string3 = "xyzabcxzyabc"
+    print(pattern_match(pattern1, string1))
+    print(pattern_match(pattern2, string2))
+    print(pattern_match(pattern3, string3))
diff --git a/graph/find_path.py b/graph/find_path.py
@@ -34,7 +34,6 @@ def find_all_path(graph, start, end, path=[]):
                 paths.append(newpath)
     return paths
 
-
 def find_shortest_path(graph, start, end, path=[]):
     path = path + [start]
     if start == end:
diff --git a/hashset/randomized_set.py b/hashset/randomized_set.py
@@ -0,0 +1,40 @@
+"""
+Design a data structure that supports all following operations
+in average O(1) time.
+
+insert(val): Inserts an item val to the set if not already present.
+remove(val): Removes an item val from the set if present.
+get_random: Returns a random element from current set of elements.
+           Each element must have the same probability of being returned.
+"""
+
+
+class RandomizedSet():
+    """
+    idea:
+        shit
+    """
+    def __init__(self):
+        pass
+
+    def insert(self, val):
+        pass
+
+    def remove(self, val):
+        pass
+
+    def get_random(self):
+        pass
+
+
+if __name__ == "__main__":
+    rset = RandomizedSet()
+    rset.insert(1)
+    rset.insert(2)
+    rset.insert(3)
+
+    rset.remove(2)
+
+    print(rset.get_random())
+    print(rset.get_random())
+    print(rset.get_random())
