Fixed solutions

shichao-an · shichao-an · commit 768050ca3a89 · 2015-09-02T18:23:54.000-07:00
diff --git a/minimum_path_sum/solution.py b/minimum_path_sum/solution.py
@@ -1,3 +1,10 @@
+"""
+Given a m x n grid filled with non-negative numbers, find a path from top left
+to bottom right which minimizes the sum of all numbers along its path.
+
+Note: You can only move either down or right at any point in time.
+"""
+
 class Solution:
     # @param grid, a list of lists of integers
     # @return an integer
diff --git a/minimum_path_sum/solution2.py b/minimum_path_sum/solution2.py
@@ -1,3 +1,10 @@
+"""
+Given a m x n grid filled with non-negative numbers, find a path from top left
+to bottom right which minimizes the sum of all numbers along its path.
+
+Note: You can only move either down or right at any point in time.
+"""
+
 class Solution:
     # @param grid, a list of lists of integers
     # @return an integer
diff --git a/search_for_a_range/solution2.py b/search_for_a_range/solution2.py
@@ -0,0 +1,60 @@
+"""
+Given a sorted array of integers, find the starting and ending position of a
+given target value.
+
+Your algorithm's runtime complexity must be in the order of O(log n).
+
+If the target is not found in the array, return [-1, -1].
+
+For example,
+Given [5, 7, 7, 8, 8, 10] and target value 8,
+return [3, 4].
+"""
+
+class Solution(object):
+    def searchRange(self, nums, target):
+        """
+        :type nums: List[int]
+        :type target: int
+        :rtype: List[int]
+        """
+        n = len(nums)
+        left = 0
+        right = n - 1
+        left_res = -1
+        right_res = -1
+        # Search for left bound (first occurence of target)
+        while left + 1 < right:
+            mid = left + (right - left) / 2
+            if target > nums[mid]:
+                left = mid
+            else:
+                right = mid
+        if nums[left] == target:
+            left_res = left
+        elif nums[right] == target:
+            left_res = right
+        else:
+            return [-1, -1]
+
+        # Search for right bound (last occurence of target)
+        left = 0
+        right = n - 1
+        while left + 1 < right:
+            mid = left + (right - left) / 2
+            if target >= nums[mid]:
+                left = mid
+            else:
+                right = mid
+        if nums[right] == target:
+            right_res = right
+        elif nums[left] == target:
+            right_res = left
+        return [left_res, right_res]
+
+
+a1 = [5, 7, 7, 8, 8, 10]
+a2 = [2, 2]
+s = Solution()
+print(s.searchRange(a1, 8))
+print(s.searchRange(a2, 2))
diff --git a/triangle/solution.py b/triangle/solution.py
@@ -1,3 +1,21 @@
+"""
+Given a triangle, find the minimum path sum from top to bottom. Each step you
+may move to adjacent numbers on the row below.
+
+For example, given the following triangle
+[
+     [2],
+    [3,4],
+   [6,5,7],
+  [4,1,8,3]
+]
+The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
+
+Note:
+Bonus point if you are able to do this using only O(n) extra space, where n is
+the total number of rows in the triangle.
+"""
+
 class Solution:
     # @param triangle, a list of lists of integers
     # @return an integer
diff --git a/triangle/solution2.py b/triangle/solution2.py
@@ -0,0 +1,57 @@
+"""
+Given a triangle, find the minimum path sum from top to bottom. Each step you
+may move to adjacent numbers on the row below.
+
+For example, given the following triangle
+[
+     [2],
+    [3,4],
+   [6,5,7],
+  [4,1,8,3]
+]
+The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
+
+Note:
+Bonus point if you are able to do this using only O(n) extra space, where n is
+the total number of rows in the triangle.
+"""
+
+class Solution(object):
+    def minimumTotal(self, triangle):
+        """
+        :type triangle: List[List[int]]
+        :rtype: int
+        """
+        n = len(triangle)
+        m = 0
+        res = None
+        for i, row in enumerate(triangle):
+            m = len(row)
+            if i > 0:
+                for j, col in enumerate(row):
+                    if 0 < j < m - 1:
+                        triangle[i][j] += min(triangle[i - 1][j - 1],
+                                              triangle[i - 1][j])
+                    elif j == 0:
+                        triangle[i][j] += triangle[i - 1][j]
+                    # j == m - 1
+                    else:
+                        triangle[i][j] += triangle[i - 1][j - 1]
+            if i == n - 1:
+                for col in row:
+                    if res is None:
+                        res = col
+                    else:
+                        res = min(col, res)
+        return res
+
+
+a1 = [
+    [2],
+    [3, 4],
+    [6, 5, 7],
+    [4, 1, 8, 3]
+]
+
+s = Solution()
+print(s.minimumTotal(a1))
diff --git a/unique_paths/solution.py b/unique_paths/solution.py
@@ -1,3 +1,14 @@
+"""
+A robot is located at the top-left corner of a m x n grid (marked 'Start' in
+the diagram below).
+
+The robot can only move either down or right at any point in time. The robot
+is trying to reach the bottom-right corner of the grid (marked 'Finish' in the
+diagram below).
+
+How many possible unique paths are there?
+"""
+
 class Solution:
     # @return an integer
     def uniquePaths(self, m, n):
diff --git a/unique_paths_ii/solution.py b/unique_paths_ii/solution.py
@@ -1,3 +1,24 @@
+"""
+Follow up for "Unique Paths":
+
+Now consider if some obstacles are added to the grids. How many unique paths
+would there be?
+
+An obstacle and empty space is marked as 1 and 0 respectively in the grid.
+
+For example,
+There is one obstacle in the middle of a 3x3 grid as illustrated below.
+
+[
+  [0,0,0],
+  [0,1,0],
+  [0,0,0]
+]
+The total number of unique paths is 2.
+
+Note: m and n will be at most 100.
+"""
+
 class Solution:
     # @param obstacleGrid, a list of lists of integers
     # @return an integer
diff --git a/unique_paths_ii/solution2.py b/unique_paths_ii/solution2.py
@@ -1,3 +1,24 @@
+"""
+Follow up for "Unique Paths":
+
+Now consider if some obstacles are added to the grids. How many unique paths
+would there be?
+
+An obstacle and empty space is marked as 1 and 0 respectively in the grid.
+
+For example,
+There is one obstacle in the middle of a 3x3 grid as illustrated below.
+
+[
+  [0,0,0],
+  [0,1,0],
+  [0,0,0]
+]
+The total number of unique paths is 2.
+
+Note: m and n will be at most 100.
+"""
+
 class Solution:
     # @param obstacleGrid, a list of lists of integers
     # @return an integer
diff --git a/word_break/solution.py b/word_break/solution.py
@@ -0,0 +1,35 @@
+"""
+Given a string s and a dictionary of words dict, determine if s can be
+segmented into a space-separated sequence of one or more dictionary words.
+
+For example, given
+s = "leetcode",
+dict = ["leet", "code"].
+
+Return true because "leetcode" can be segmented as "leet code".
+"""
+
+class Solution(object):
+    def wordBreak(self, s, wordDict):
+        """
+        :type s: str
+        :type wordDict: Set[str]
+        :rtype: bool
+        """
+        t = set()
+        return self.word_break_aux(s, wordDict, t)
+
+    def word_break_aux(self, s, wordDict, t):
+        if not s:
+            return True
+        if s in t:
+            return True
+        else:
+            for i, c in enumerate(s):
+                word = s[:i + 1]
+                rest = s[i + 1:]
+                if word in wordDict and self.wordBreak(rest, wordDict):
+                    t.add(s)
+                    print(t)
+                    return True
+            return False
