String - Substring

Algorithms
string

is Substring

28. Implement strStr()

  • input : 2 string

    Solution1. Naive

  • Time : O(m * n)
  • try every possible start index in haystack
1
2
3
4
5
6
7
class Solution(object):
    def strStr(self, haystack, needle):
        m, n = len(needle), len(haystack)
        for i in xrange(n-m+1):
            if haystack[i:i+m] == needle:
                return i
        return -1

Solution2. KMP

  • Time : O(m + n)
  • know the basic idea of KMP and can walk through some test cases
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    class Solution(object):
        def getNext(self, pattern):
            m = len(pattern)
            next = [0] * m
            k = 0
            for i in xrange(1, m):
                while k > 0 and pattern[k] != pattern[i]:
                    k = next[k-1]
                if pattern[k] == pattern[i]:
                    k += 1
                next[i] = k
            return next

        def strStr(self, haystack, needle):
            if not needle:
                return 0
            next = self.getNext(needle)
            n = len(haystack)
            p = 0
            for i in xrange(n):
                while p > 0 and needle[p] != haystack[i]:
                    p = next[p-1]
                if needle[p] == haystack[i]:
                    p += 1
                if p == len(needle):
                    return i-len(needle)+1
            return -1

Solution3. Robin-Karp

  • Time : O(m+n)
  • Principle: if we can hash the short string to a hashed value (e.g. integer, which is unique). Then we can just compare each substring of s1’s hashed value and compare it with s2’s hash value.
  • Assumption: only lower case letter (base = 26 a–z)
  • Each time you slide the window, add right, delete left and times 26 in the middle!!!

Sliding Window

A string has $n^2$ substrings! These type of question ask you to find a subtring meet some certain condition!

  1. When to move the right pointer and when to move the left pointer
  2. use hashset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        visited = set()
        left = right = 0
        res = 0
        while right < len(s):
            if s[right] not in visited:
                visited.add(s[right])
                res = max(res, right-left+1)
                right += 1
            else:
                visited.remove(s[left])
                left += 1
        return res

159. Longest Substring with At Most Two Distinct Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        dic = {}
        n = len(s)
        cnt = 0
        left = right = 0
        res = 0
        while right < n:
            if s[right] in dic:
                dic[s[right]] += 1
                right += 1
            else:
                while cnt >= 2:
                    dic[s[left]] -= 1
                    if dic[s[left]] == 0:
                        cnt -= 1
                        del dic[s[left]]
                    left += 1
                dic[s[right]] = 1
                cnt += 1
                right += 1
            res = max(res, right-left)
        return res

340. Longest Substring with At Most K Distinct Characters

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def lengthOfLongestSubstringKDistinct(self, s, k):
        chars = [0] * 256
        start = 0
        res = cnt = 0
        for i in xrange(len(s)):
            idx = ord(s[i])
            if chars[idx] == 0:
                cnt += 1
            chars[idx] += 1

            while cnt > k:
                idx = ord(s[start])
                chars[idx] -= 1
                if chars[idx] == 0:
                    cnt -= 1
                start += 1
            res = max(res, i-start+1)
        return res

76. Minimum Window Substring

  • it will be easy to let right pointer be the iteration pointer
  • cnt is the flag to show whether it satisfies the condition
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    class Solution(object):
        def minWindow(self, s, t):
          tmap = {}
          for c in t:
              tmap[c] = tmap.get(c, 0) + 1

          cnt = len(t)
          start = 0
          res, ret = len(s)+1, ""
          for i in xrange(len(s)):
              if s[i] in tmap:
                  tmap[s[i]] -= 1
                  if tmap[s[i]] >= 0:
                      cnt -= 1

              while cnt == 0:
                  win = i-start+1
                  if win < res:
                      res = win
                      ret = s[start:i+1]
                  if s[start] in tmap:
                      if tmap[s[start]] >= 0:
                          cnt += 1
                      tmap[s[start]] += 1
                  start += 1
          return ret

438. Find All Anagrams in a String

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution(object):
    def findAnagrams(self, s, p):
        if len(s) < len(p):
            return []

        dic = collections.defaultdict(int)
        for ch in p:
            dic[ch] += 1

        cnt = len(dic.keys())
        k = len(p)
        for i in range(k):
            if s[i] in dic:
              dic[s[i]] -= 1
              if dic[s[i]] == 0:
                  cnt -= 1

        res = []
        if cnt == 0:
            res.append(0)

        for i in range(k, len(s)):
            if s[i] in dic:
                dic[s[i]] -= 1
                if dic[s[i]] == 0:
                    cnt -= 1

            if s[i-k] in dic:
                dic[s[i-k]] += 1
                if dic[s[i-k]] == 1:
                    cnt += 1

            if cnt == 0:
                res.append(i-k+1)
        return res
Share

Input are Points

Algorithms
topic

Lies inside or outside

Point Lies inside or outside a polygon

  1. Draw a horizontal line to the right of each point and extend it to infinity
  2. Count the number of times the line intersects with polygon edges.
  3. A point is inside the polygon if either count of intersections is odd or point lies on an edge of polygon. If none of the conditions is true, then point lies outside.

TODO

939. Minimum Area Rectangle

Given some points, please calculate the minimum Rectangle.
Height and width must be parallel to axes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def minAreaRect(self, points):
        pset = set()
        for x, y in points:
            pset.add((x, y))

        n = len(points)
        res = float('inf')
        for i in range(n):
            for j in range(i+1, n):
                x1, y1 = points[i]
                x2, y2 = points[j]
                if x1 == x2 or y1 == y2:
                    continue
                if (x1, y2) not in pset or (x2, y1) not in pset:
                    continue

                res = min(res, abs(x2-x1) * abs(y2-y1))
        return 0 if res == float('inf') else res

Share

String Parenthesis

Algorithms
dfs, string

678. Valid Parenthesis String

  • If you use stack to solve this question, it will be complex to handle different cases!
  • If you use dfs to search if is valid, it will be time consuming!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def checkValidString(self, s):
        low = high = 0
        for ch in s:
            if ch == '(':
                low += 1
                high += 1
            elif ch == ')':
                low = max(0, low-1)
                high -= 1
                if high < 0:
                    return False
            else: # "*"
                low = max(0, low-1)
                high += 1
        return low == 0

22. Generate Parentheses

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def generateParenthesis(self, n):
        res = []
        self.dfs(0, 0, n, [], res)
        return res

    def dfs(self, left, right, n, path, res):
        if right == n:
            res.append(''.join(path))
            return

        if left < n:
            self.dfs(left + 1, right, n, path + ['('], res)

        if right < left:
            self.dfs(left, right + 1, n, path + [')'], res)
  • Follow up : 3 {}, 2(), 1[]
Share

Tree Definition

Algorithms
tree

Definition of Tree

  • at most two children node
1
2
3
4
5
6
# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

Application

  • Social networks analysis
  • Information indexing
  • Information compression

388. Longest Absolute File Path

  • use Stack to simulate the traversal of file system
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def lengthLongestPath(self, input):
        def countT(s):
            cnt = 0
            for ch in s:
                if ch == '\t':
                    cnt += 1
                else:
                    return cnt
            return cnt

        dirs = input.split('\n')
        res = 0
        stack = []
        for i in range(len(dirs)):
            path = dirs[i]
            n = countT(path)
            while n < len(stack):
                stack.pop()
            stack.append(path[n:])
            if '.' in stack[-1]:
                res = max(res, len('/'.join(stack)))
        return res

Terms

  • Balanced Binary Tree
    Balanced Binary Tree is commonly defined as a binary tree in which the depth of the left and right subtrees of every node differ by 1 or less
  • Complete Binary Tree
    Complete Binary Tree is a banary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
  • Binary Search Tree
    Binary Search Tree is for every sigle node in the tree, the values in its left subtree are all smaller than its value, and the values in its right subtree are all larger than its value.

919. Complete Binary Tree Inserter

Solution1. Array

  • For Complete Binary Search Tree, we can use an array to save all the node index! Then we can find its parent using the index relation!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class CBTInserter:
    # Space : O(n) n is the number of the nodes
    def __init__(self, root):
        self.nodes = []
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()
            self.nodes.append(node)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

    # Time : O(1)            
    def insert(self, v):
        n = len(self.nodes)
        parent = self.nodes[(n - 1) // 2]
        node = TreeNode(v)
        self.nodes.append(node)
        if n % 2 == 1:
            parent.left = node
        else:
            parent.right = node
        return parent.val


    def get_root(self):
        return self.nodes[0]

Solution2. Deque

  • Have the Same time and space complexity, but actually use half spaces than sol1!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    class CBTInserter:

        def __init__(self, root):
            self.root = root
            self.deque = collections.deque()
            queue = collections.deque([root])
            while queue:
                node = queue.popleft()
                if not node.left or not node.right:
                    self.deque.append(node)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

        def insert(self, v):
            node = TreeNode(v)
            parent = self.deque[0]
            if not parent.left:
                parent.left = node
            else:
                parent.right = node
                self.deque.popleft()
            self.deque.append(node)
            return parent.val

        def get_root(self):
            return self.root

222. Count Complete Tree Nodes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def countNodes(self, root):
        if not root:
            return 0
        left = self.getDepth(root.left)
        right = self.getDepth(root.right)
        if left == right:
            return (2**left) + self.countNodes(root.right)
        else:
            return (2**right) + self.countNodes(root.left)


    def getDepth(self, root):
        if not root:
            return 0
        cnt = 0
        cur = root
        while cur:
            cur = cur.left
            cnt += 1
        return cnt

Follow Up

  • Given the key n, binary tree key is [1, 2, 3, 4 …], how to check if the node with key n in the complete binary tree ?
    Time : O(log n)
  • Can you count the number of nodes in complete binary tree, based on previous question?
    Binary Search + Previous Question. Time ($(logn)^2$)
Share

Two Pinters

Algorithms
topic

Same Direction

27. Remove Element

  • left pointer represents the postion that next valid result will be put in!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # Time : O(n), Sapce : O(1)
    class Solution(object):
        def removeElement(self, nums, val):
            left = 0
            for i in range(len(nums)):
                if nums[i] != val:
                    nums[left] = nums[i]
                    left += 1
            return left

26. Remove Duplicates from Sorted Array

  • first pointer represents the last position in the result!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # Time : O(n), Sapce : O(1)
    class Solution(object):
        def removeDuplicates(self, nums):
            if not nums:
                return 0

            first = 0
            for i in range(1, len(nums)):
                if nums[i] != nums[first]:
                    first += 1
                    nums[first] = nums[i]
            return first+1

80. Remove Duplicates from Sorted Array II

  • small trick: 1. start interation from index 2, 2. comprare with the element with only the second last element!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    # Time : O(n), Sapce : O(1)
    class Solution(object):
        def removeDuplicates(self, nums):
            n = len(nums)
            if n <= 2:
                return n

            first = 1
            for i in range(2, n):
                if nums[i] != nums[first-1]:
                    first += 1
                    nums[first] = nums[i]
            return first + 1

Two Sequence

88. Merge Sorted Array

  • two pointers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def merge(self, nums1, m, nums2, n):
        p1, p2 = m - 1, n - 1
        p = m + n - 1
        while p1 >= 0 and p2 >= 0:
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            p -= 1

        while p2 >= 0:
            nums1[p] = nums2[p2]
            p -= 1
            p2 -= 1
Share

String Subsequence

Algorithms
string
  • For a string with length n, it has $2^n$ Subsequences
  • Check a string is or not a subsequence of another string (a litte greedy)

    392. Is Subsequence

  • Time : O(|t|)

Solution1. Recursion

1
2
3
4
5
6
7
8
9
class Solution:
    def isSubsequence(self, s, t):
        if not s:
            return True

        for i in range(len(t)):
            if t[i] == s[0]:
                return self.isSubsequence(s[1:], t[i+1:])
        return False

Solution2. Iteration

  • Two Pointer and Greedy
    1
    2
    3
    4
    5
    6
    7
    8
    9
    class Solution:
        def isSubsequence(self, s, t):
            p = 0
            for i in range(len(t)):
                if p >= len(s):
                    break
                if s[p] == t[i]:
                    p += 1
            return p == len(s)

Follow up : multiple strings

If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence.

  • intuitive way is to precalculate something in T to speed up the query
  • Precalculate : O(n), Query : (mlogn)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def isSubsequence(self, s, t):
        indices = collections.defaultdict(list)
        for i, ch in enumerate(t):
            indices[ch].append(i)

        prev = -1
        for i in range(len(s)):
            if s[i] not in indices:
                return False
            idx = self.bSearch(prev, indices[s[i]])
            if idx == -1:
                return False
            prev = idx
        return True

    def bSearch(self, prev, nums):
        if prev >= nums[-1]:
            return -1

        start, end = 0, len(nums) - 1
        while start < end:
            mid = start + (end - start) // 2
            if nums[mid] > prev: # Mistake2 : we should find greater than previous index CANNOT equal
                end = mid
            else:
                start = mid + 1

        return nums[start] if nums[start] > prev else -1
        # Mistake1 : forget to consider the index may not in the nums!!!

792. Number of Matching Subsequences

Solution1. Binary Search + Hash Table

  • Online Algorithms, Precalculate String
  • Data Structure : Hash Table <charater, indices>
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    class Solution:
        def numMatchingSubseq(self, S, words):
            # Time O(n)
            indices = [[] for _ in range(26)]
            for i, ch in enumerate(S):
                indices[ord(ch)-ord('a')].append(i)

            cnt = 0
            mdic = {}
            for word in words:
                if word in mdic:
                    cnt += mdic[word]
                    continue

                if self.isMatch(indices, word):
                    mdic[word] = 1
                    cnt += 1
                else:
                    mdic[word] = 0

            return cnt

        # Time : O(mlog n) n is the length of S, m is the length of word
        def isMatch(self, indices, word):
            prev = -1
            for ch in word:
                idx = self.bSearch(prev, indices[ord(ch)-ord('a')])
                if idx == -1:
                    return False
                prev = idx
            return True

        def bSearch(self, prev, nums):
            if not nums or prev >= nums[-1]:
                return -1

            start, end = 0, len(nums) - 1
            while start < end:
                mid = start + (end - start) // 2
                if nums[mid] > prev:
                    end = mid
                else:
                    start = mid + 1
            return nums[start] if nums[start] > prev else -1

Solution2. Next Letter Pointer

  • Offline Algorithms, Precalculate words
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def numMatchingSubseq(self, S, words):
        indices = [[] for _ in range(26)]
        for word in words:
            indices[ord(word[0]) - ord('a')].append(word[1:])

        cnt = 0
        for ch in S:
            cans = indices[ord(ch)-ord('a')]
            newCans = []
            for can in cans:
                if len(can) == 0:
                    cnt += 1
                    continue
                if can[0] == ch:
                    newCans.append(can[1:])
                else:
                    indices[ord(can[0])-ord('a')].append(can[1:])
            indices[ord(ch)-ord('a')] = newCans
        return cnt

727. Minimum Window Subsequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def minWindow(self, S, T):
        n = len(S)
        # Must be the start index of the results!!!
        cur = [i if S[i] == T[0] else -1 for i in range(n)]

        for j in xrange(1, len(T)):
            last = -1
            new = [-1] * n
            for i, ch in enumerate(S):
                if last >= 0 and ch == T[j]:
                    new[i] = last
                if cur[i] >= 0:
                    last = cur[i]
            cur = new

        start, end = 0, n
        for e, s in enumerate(cur):
            if s >= 0 and e - s < end - start:
                start, end = s, e
        return S[start:end+1] if end != n else ""
Share

DP Bag

Algorithms
TODO, dp

279. Perfect Squares

Solution1. DP - TLE

  • Time O($n\sqrt{n}$), Space: O(n)
  • have no idea why works in python2, but TLE in python3
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def numSquares(self, n):
        dp = [float('inf')] * (n+1)
        dp[0] = 0
        for i in range(1, n+1):
            j = 1
            while (j * j <= i):
                if dp[i-j*j] + 1 < dp[i]:
                    dp[i] = dp[i-j*j] + 1
                j += 1
        return dp[-1]

Solution2. BFS

  • Consider a graph which consists of number 0, 1,…,n as its nodes.
  • Node j is connected to node i via an edge if and only if either j = i + (a perfect square number) or i = j + (a perfect square number). Starting from node 0, do the breadth-first search.
  • If we reach node n at step m, then the least number of perfect square numbers which sum to n is m. Here since we have already obtained the perfect square numbers, we have actually finished the search at step 1.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution:
        def numSquares(self, n):
            cans = []
            i = 1
            while i * i <= n:
                cans.append(i * i)
                i += 1

            queue = [n]
            level = 0
            while queue:
                level += 1
                nqueue = set()
                for remain in queue:
                    for can in cans:
                        if can == remain:
                            return level
                        if can > remain:
                            break
                        nqueue.add(remain-can)
                queue = list(nqueue)

322. Coin Change

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def coinChange(self, coins, amount):
        if amount == 0:
            return 0

        dp = [float('inf')] * (amount+1)
        dp[0] = 0

        for i in xrange(1, amount+1):
            for coin in coins:
                if i-coin >= 0:
                    dp[i] = min(dp[i], dp[i-coin]+1)

        return -1 if dp[-1] == float('inf') else dp[-1]

Count

518. Coin Change 2

  • Why use for loop in this order??? coin first, then amount?
    1
    2
    3
    4
    5
    6
    7
    8
    class Solution(object):
        def change(self, amount, coins):
            dp = [0] * (amount+1)
            dp[0] = 1
            for coin in coins:
                for i in range(coin, amount+1):
                    dp[i] += dp[i-coin]
            return dp[-1]
Share

String Pattern

Algorithms
string

290. Word Pattern

  • Why we need Two HashTable?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def wordPattern(self, pattern, str):
        words = str.split()
        m, n = len(pattern), len(words)
        if m != n:
            return False
        dic = {}
        used = set()
        for i in range(m):
            if pattern[i] not in dic:
                if words[i] in used:
                    return False
                dic[pattern[i]] = words[i]
                used.add(words[i])
            else:
                if dic[pattern[i]] != words[i]:
                    return False
        return True

291. Word Pattern II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def wordPatternMatch(self, pattern, str):
        return self.isMatch(pattern, str, {}, set())

    def isMatch(self, pattern, s, dic, used):
        if not pattern and not s:
            return True
        elif not pattern or not s:
            return False

        ch = pattern[0]
        if ch in dic:
            word = dic[ch]
            n = len(word)
            if word == s[:n]:
                return self.isMatch(pattern[1:], s[n:], dic, used)
            else:
                return False
        else:
            for i in range(len(s)):
                if s[:i+1] in used:
                    continue
                dic[ch] = s[:i+1]
                used.add(s[:i+1])
                if self.isMatch(pattern[1:], s[i+1:], dic, used):
                    return True
                used.remove(s[:i+1])
                del dic[ch]
            return False

809. Expressive Words

  • pairs <character, counter>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
    def expressiveWords(self, S, words):
        pairs = []
        for i in range(len(S)):
            if not pairs or S[i] != pairs[-1][0]:
                pairs.append([S[i], 1])
            else:
                pairs[-1][1] += 1

        cnt = 0
        for word in words:
            if self.isExtended(pairs, word):
                cnt += 1
        return cnt

    def isExtended(self, pairs, word):
        i = 0
        for j in range(len(pairs)):
            ch, cnt = pairs[j]
            if cnt < 3:
                while cnt:
                    if i >= len(word) or ch != word[i]:
                        return False
                    cnt -= 1
                    i += 1
            else:
                ncnt = 0
                while i < len(word) and word[i] == ch:
                    i += 1
                    ncnt += 1

                if ncnt == 0 or ncnt > cnt:
                    return False
        return i == len(word)

890. Find and Replace Pattern

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findAndReplacePattern(self, words, pattern):
        res = []
        for word in words:
            if self.isMatched(word, pattern):
                res.append(word)
        return res

    def isMatched(self, word, pattern):
        mapw = {}
        mapp = {}
        for ch1, ch2 in zip(word, pattern):
            if ch1 not in mapw:
                mapw[ch1] = ch2
            else:
                if mapw[ch1] != ch2:
                    return False

            if ch2 not in mapp:
                mapp[ch2] = ch1
            else:
                if mapp[ch2] != ch1:
                    return False
        return True
Share

DP - Matrix

Algorithms
dp

Count

62. Unique Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
# Time : O(mn), Space : O(mn)
class Solution:
    def uniquePaths(self, m, n):
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1

        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
# Time : O(mn), Space : O(n)
class Solution:
    def uniquePaths(self, m, n):
        dp = [1] * n

        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
        return dp[-1]

Follow Up

  1. Given three points in the matrix, find the path number that traverse these 3 points
  • do it seperated three matrix, then add together
  1. How to validate the three points?
  2. If give you a “H”, ask your path have to cross “H”

63. Unique Paths II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        if not obstacleGrid:
            return 0
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [0] * (n + 1)
        dp[0] = 1
        for i in range(n):
            dp[i+1] = 0 if obstacleGrid[0][i] else dp[i]

        for i in range(1, m):
            if obstacleGrid[i][0] == 1:
                dp[1] = 0  
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    dp[j+1] = 0
                else:
                    dp[j+1] += dp[j]
        return dp[-1]

118. Pascal’s Triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def generate(self, numRows):
        if numRows == 0:
            return []

        res = [[1]]
        for i in range(1, numRows):
            cur = [1]
            for j in range(1, i):
                cur.append(res[-1][j-1] + res[-1][j])
            cur.append(1)
            res.append(cur)
        return res

119. Pascal’s Triangle II

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def getRow(self, rowIndex):
        if rowIndex == 0:
            return [1]

        prev = [1]
        for i in range(1, rowIndex+1):
            cur = [1]
            for j in range(1, i):
                cur.append(prev[j-1]+prev[j])
            cur += [1]
            prev = cur
        return cur

Minimum

64. Minimum Path Sum

  • Time : O(mn), Space : O(min(m, n))
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    class Solution(object):
        def minPathSum(self, grid):
            if not grid:
                return 0

            m, n = len(grid), len(grid[0])

            dp = [0] * n
            for i in range(n):
                dp[i] = grid[0][i] + (dp[i-1] if i >0 else 0)

            for i in range(1, m):
                for j in range(n):
                    if j == 0:
                        dp[j] += grid[i][j]
                        continue
                    dp[j] = min(dp[j], dp[j-1]) + grid[i][j]
            return dp[-1]
Share

DFS - Matrix

Algorithms
dfs

329. Longest Increasing Path in a Matrix

  • DFS search + Memorization in Matrix!!!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Time : O(mn), Space : O(mn)
class Solution:
    def longestIncreasingPath(self, matrix):
        if not matrix:
            return 0

        m, n = len(matrix), len(matrix[0])
        self.visited = {}
        res = 0
        for i in range(m):
            for j in range(n):
                ans = self.dfs(matrix, -float('inf'), i, j)
                res = max(res, ans)
        return res


    def dfs(self, matrix, prev, i, j):
        m, n = len(matrix), len(matrix[0])
        if i < 0 or j < 0 or i > m-1 or j > n-1:
            return 0

        val = matrix[i][j]
        if val <= prev:
            return 0

        if (i, j) in self.visited:
            return self.visited[(i, j)]

        d1 = self.dfs(matrix, val, i+1, j)
        d2 = self.dfs(matrix, val, i, j+1)
        d3 = self.dfs(matrix, val, i-1, j)
        d4 = self.dfs(matrix, val, i, j-1)
        d = max(d1, d2, d3, d4) + 1
        self.visited[(i, j)] = d
        return d

36. Valid Sudoku

  • but only meet the condition showed below can Not make sure the sudoku is valid!!!
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    class Solution:
        def isValidSudoku(self, board):
            rows = [set() for _ in range(9)]
            cols = [set() for _ in range(9)]
            cubs = [set() for _ in range(9)]
            for i in range(9):
                for j in range(9):
                    if board[i][j] == '.':
                        continue
                    num = board[i][j]
                    c = i // 3 * 3 + j // 3

                    if num in rows[i] or num in cols[j] or num in cubs[c]:
                        return False

                    rows[i].add(num)
                    cols[j].add(num)
                    cubs[c].add(num)
            return True

37. Sudoku Solver

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution:
    def solveSudoku(self, board):
        self.solve(board)

    def solve(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    continue

                for ch in list("123456789"):
                    if self.isValid(board, i, j, ch):
                        board[i][j] = ch
                        if self.solve(board):
                            return True
                        else:
                            board[i][j] = '.'
                return False
        return True

    def isValid(self, board, i, j, ch):
        # row & col
        for k in range(9):
            if board[i][k] == ch:
                return False

            if board[k][j] == ch:
                return False

        # cubes
        row, col = (i // 3) * 3, (j // 3) * 3
        for r in range(3):
            for c in range(3):
                if board[row + r][col + c] == ch:
                    return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
    def solveSudoku(self, board):
        self.solve(board)

    def solve(self, board):
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    continue

                candidates = self.getCandidates(board, i, j)
                for ch in candidates:
                    board[i][j] = ch
                    if self.solve(board):
                        return True
                    else:
                        board[i][j] = '.'
                return False
        return True

    def getCandidates(self, board, i, j):
        cans = set(list("123456789"))
        for k in range(9):
            ch = board[i][k]
            if ch != '.' and ch in cans:
                cans.remove(board[i][k])

            ch = board[k][j]
            if ch != '.' and ch in cans:
                cans.remove(board[k][j])

        row, col = (i // 3) * 3, (j // 3) * 3
        for r in range(3):
            for c in range(3):
                ch = board[row + r][col + c]
                if ch != '.' and ch in cans:
                    cans.remove(ch)
        return list(cans)

489. Robot Room Cleaner

  • The main different thing between this dfs and others is that you have to Maintain the Direction!!!
  • Backtrack: turn 2 times to revert, move 1 step, and turn 2 times to revert back.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    class Solution(object):
        def cleanRoom(self, robot):
            visited = set()
            self.dfs(robot, 0, 0, 0, visited)

        def dfs(self, robot, i, j, k, visited):
            robot.clean()
            visited.add((i, j))

            dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
            for _ in range(4):
                di, dj = dirs[k]
                ni, nj = i + di, j + dj
                if (ni, nj) not in visited and robot.move():
                    self.dfs(robot, ni, nj, k, visited)
                    robot.turnLeft()
                    robot.turnLeft()
                    robot.move()
                    robot.turnLeft()
                    robot.turnLeft()
                robot.turnLeft()
                k = (k + 1) % 4

Share