dp and stuff

keon · keon · commit 24db4c4a0948 · 2017-01-01T15:32:20.000-05:00
diff --git a/bfs/word_ladder.py b/bfs/word_ladder.py
@@ -0,0 +1,62 @@
+"""
+Given two words (beginWord and endWord), and a dictionary's word list,
+find the length of shortest transformation sequence
+from beginWord to endWord, such that:
+
+Only one letter can be changed at a time
+Each intermediate word must exist in the word list
+For example,
+
+Given:
+beginWord = "hit"
+endWord = "cog"
+wordList = ["hot","dot","dog","lot","log"]
+As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
+return its length 5.
+.
+Note:
+Return 0 if there is no such transformation sequence.
+All words have the same length.
+All words contain only lowercase alphabetic characters.
+"""
+def ladderLength(beginWord, endWord, wordList):
+    """
+    Bidirectional BFS!!!
+    :type beginWord: str
+    :type endWord: str
+    :type wordList: Set[str]
+    :rtype: int
+    """
+    beginSet = set()
+    endSet = set()
+    beginSet.add(beginWord)
+    endSet.add(endWord)
+    result = 2
+    while len(beginSet) != 0 and len(endSet) != 0:
+        if len(beginSet) > len(endSet):
+            beginSet, endSet = endSet, beginSet
+        nextBeginSet = set()
+        for word in beginSet:
+            for ladderWord in wordRange(word):
+                if ladderWord in endSet:
+                    return result
+                if ladderWord in wordList:
+                    nextBeginSet.add(ladderWord)
+                    wordList.remove(ladderWord)
+        beginSet = nextBeginSet
+        result += 1
+        print(beginSet)
+        print(result)
+    return 0
+
+def wordRange(word):
+    for ind in range(len(word)):
+        tempC = word[ind]
+        for c in [chr(x) for x in range(ord('a'), ord('z')+1)]:
+            if c != tempC:
+                yield word[:ind] + c + word[ind+1:]
+
+beginWord = "hit"
+endWord = "cog"
+wordList = ["hot","dot","dog","lot","log"]
+print(ladderLength(beginWord, endWord, wordList))
diff --git a/divide-and-conquer/expression_add_operators.py b/divide-and-conquer/expression_add_operators.py
diff --git a/divide-and-conquer/the_skyline_problem.py b/divide-and-conquer/the_skyline_problem.py
diff --git a/dp/combination_sum4.py b/dp/combination_sum4.py
@@ -0,0 +1,63 @@
+Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
+
+Example:
+
+nums = [1, 2, 3]
+target = 4
+
+The possible combination ways are:
+(1, 1, 1, 1)
+(1, 1, 2)
+(1, 2, 1)
+(1, 3)
+(2, 1, 1)
+(2, 2)
+(3, 1)
+
+Note that different sequences are counted as different combinations.
+
+Therefore the output is 7.
+Follow up:
+What if negative numbers are allowed in the given array?
+How does it change the problem?
+What limitation we need to add to the question to allow negative numbers?
+
+
+private int[] dp;
+
+public int combinationSum4(int[] nums, int target) {
+    dp = new int[target + 1];
+    Arrays.fill(dp, -1);
+    dp[0] = 1;
+    return helper(nums, target);
+}
+
+private int helper(int[] nums, int target) {
+    if (dp[target] != -1) {
+        return dp[target];
+    }
+    int res = 0;
+    for (int i = 0; i < nums.length; i++) {
+        if (target >= nums[i]) {
+            res += helper(nums, target - nums[i]);
+        }
+    }
+    dp[target] = res;
+    return res;
+}
+
+
+EDIT: The above solution is top-down. How about a bottom-up one?
+
+public int combinationSum4(int[] nums, int target) {
+    int[] comb = new int[target + 1];
+    comb[0] = 1;
+    for (int i = 1; i < comb.length; i++) {
+        for (int j = 0; j < nums.length; j++) {
+            if (i - nums[j] >= 0) {
+                comb[i] += comb[i - nums[j]];
+            }
+        }
+    }
+    return comb[target];
+}
diff --git a/stack/simplify_path.py b/stack/simplify_path.py
@@ -0,0 +1,32 @@
+"""
+Given an absolute path for a file (Unix-style), simplify it.
+
+For example,
+path = "/home/", => "/home"
+path = "/a/./b/../../c/", => "/c"
+
+* Did you consider the case where path = "/../"?
+    In this case, you should return "/".
+* Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
+    In this case, you should ignore redundant slashes and return "/home/foo".
+"""
+
+def simplify_path(path):
+    """
+    :type path: str
+    :rtype: str
+    """
+    skip = set(['..','.',''])
+    stack = []
+    paths = path.split('/')
+    for tok in paths:
+        if tok == '..':
+            if stack:
+                stack.pop()
+        elif tok not in skip:
+            stack.append(tok)
+    return '/' +'/'.join(stack)
+
+p = '/my/name/is/..//keon'
+print(p)
+print(simplify_path(p))
diff --git a/string/int_to_roman.py b/string/int_to_roman.py
@@ -0,0 +1,17 @@
+"""
+Given an integer, convert it to a roman numeral.
+Input is guaranteed to be within the range from 1 to 3999.
+"""
+
+def int_to_roman(num):
+    """
+    :type num: int
+    :rtype: str
+    """
+    M = ["", "M", "MM", "MMM"];
+    C = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
+    X = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
+    I = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
+    return M[num//1000] + C[(num%1000)//100] + X[(num%100)//10] + I[num%10];
+
+print(int_to_roman(644))
diff --git a/string/roman_to_int.py b/string/roman_to_int.py
@@ -0,0 +1,22 @@
+"""
+Given a roman numeral, convert it to an integer.
+Input is guaranteed to be within the range from 1 to 3999.
+"""
+
+
+def roman_to_int(s):
+    """
+    :type s: str
+    :rtype: int
+    """
+    number = 0
+    roman = {'M':1000, 'D':500, 'C': 100, 'L':50, 'X':10, 'V':5, 'I':1}
+    for i in range(len(s)-1):
+        if roman[s[i]] < roman[s[i+1]]:
+            number -= roman[s[i]]
+        else:
+            number += roman[s[i]]
+    return number + roman[s[-1]]
+
+r = "DCXXI"
+print(roman_to_int(r))
diff --git a/trie/add_and_search.py b/trie/add_and_search.py
@@ -13,12 +13,13 @@
 search(“.ad”) -> true
 search(“b..”) -> true
 """
+import collections
 
 class TrieNode(object):
-    def __init__(self, letter, isTerminal=False):
+    def __init__(self, letter, is_terminal=False):
         self.children = dict()
         self.letter = letter
-        self.isTerminal = isTerminal
+        self.is_terminal = is_terminal
 
 class WordDictionary(object):
     def __init__(self):
@@ -30,7 +31,7 @@ def addWord(self, word):
             if letter not in cur.children:
                 cur.children[letter] = TrieNode(letter)
             cur = cur.children[letter]
-        cur.isTerminal = True
+        cur.is_terminal = True
 
     def search(self, word, node=None):
         cur = node
@@ -41,7 +42,7 @@ def search(self, word, node=None):
             if letter == ".":
                 if i == len(word) - 1: # if last character
                     for child in cur.children.itervalues():
-                        if child.isTerminal:
+                        if child.is_terminal:
                             return True
                     return False
                 for child in cur.children.itervalues():
@@ -52,5 +53,27 @@ def search(self, word, node=None):
             if letter not in cur.children:
                 return False
             cur = cur.children[letter]
-        return cur.isTerminal
+        return cur.is_terminal
 
+class WordDictionary2(object):
+    def __init__(self):
+        self.word_dict = collections.defaultdict(list)
+
+
+    def addWord(self, word):
+        if word:
+            self.word_dict[len(word)].append(word)
+
+    def search(self, word):
+        if not word:
+            return False
+        if '.' not in word:
+            return word in self.word_dict[len(word)]
+        for v in self.word_dict[len(word)]:
+            # match xx.xx.x with yyyyyyy
+            for i, ch in enumerate(word):
+                if ch != v[i] and ch != '.':
+                    break
+            else:
+                return True
+        return False
