add some more

keon · keon · commit ea31df4223b4 · 2016-12-28T16:20:28.000-05:00
diff --git a/dp/word_break.py b/dp/word_break.py
@@ -0,0 +1,19 @@
+def word_break(s, word_dict):
+  """
+  :type s: str
+  :type word_dict: Set[str]
+  :rtype: bool
+  """
+  f = [False] * (len(s)+1)
+  f[0] = True
+  for i in range(1, len(s)+1):
+      for j in range(0, i):
+        if f[j] and s[j:i] in word_dict:
+            f[i] = True
+            break
+  return f[-1]
+
+s = "keonkim"
+dic = ["keon", "kim"]
+
+print(word_break(s, dic))
diff --git a/linkedlist/is_palindrome.py b/linkedlist/is_palindrome.py
@@ -0,0 +1,48 @@
+def is_palindrome(head):
+    if not head:
+        return True
+    # split the list to two parts
+    fast, slow = head.next, head
+    while fast and fast.next:
+        fast = fast.next.next
+        slow = slow.next
+    second = slow.next
+    slow.next = None # Don't forget here! But forget still works!
+    # reverse the second part
+    node = None
+    while second:
+        nxt = second.next
+        second.next = node
+        node = second
+        second = nxt
+    # compare two parts
+    # second part has the same or one less node
+    while node:
+        if node.val != head.val:
+            return False
+        node = node.next
+        head = head.next
+    return True
+
+def is_palindrome_stack(head):
+    if not head or not head.next:
+        return True
+
+    # 1. Get the midpoint (slow)
+    slow = fast = cur = head
+    while fast and fast.next:
+        fast, slow = fast.next.next, slow.next
+
+    # 2. Push the second half into the stack
+    stack = [slow.val]
+    while slow.next:
+        slow = slow.next
+        stack.append(slow.val)
+
+    # 3. Comparison
+    while stack:
+        if stack.pop() != cur.val:
+            return False
+        cur = cur.next
+
+    return True
diff --git a/sorting/sort_colors.py b/sorting/sort_colors.py
@@ -0,0 +1,15 @@
+def sort_colors(nums):
+    i = j = 0
+    for k in range(len(nums)):
+        v = nums[k]
+        nums[k] = 2
+        if v < 2:
+            nums[j] = 1
+            j += 1
+        if v == 0:
+            nums[i] = 0
+            i += 1
+
+nums = [0,1,1,1,2,2,2,1,1,1,0,0,0,0,1,1,1,0,0,2,2]
+sort_colors(nums)
+print(nums)
