[Leetcode] 131. Palindrome Partitioning

Well, doing leetcode problems can be addictive - I used to go to Facebook everyday - not any more and I don't feel missed at all. Now, somehow I must do some leetcode problems, otherwise I just feel wrong. It sometimes gets hard and frustrating. But I guess as I read it somewhere, in our nature human beings just love something bitter, like beer, coffee, as well as challenges (but have to be meaningful and able to make progress and intellectually fulfilling, at least for me).

---

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

This problem is similar to subset problem, my solution is not the "optimal" one, but very intuitive.

class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        if len(s) == 0: return [[]]
        if len(s) == 1: return [[s]]
        
        res = []
        for i in range(1, len(s)+1):
            part1 = s[:i]
            part2 = s[i:]
            #print part1, part2
            if part1 == part1[::-1]:
                tmp_res = self.partition(part2)
                #print tmp_res
                for r in tmp_res:
                    res.append([part1] + r)
        return res

[Leetcode] 145. Binary Tree Postorder Traversal

This is not a hard problem compared to some really hard ones. The key is to flag every node, if first in stack, 1, if all its children are in the stack, mark it as 2. Later, when encounter a node, if its flag is 1, then we push its children in the stack and mark it as 2; if it's 2, then we pop it and record the result. The order to put the children? First right, then left --> then we are able to see left first and then the right.

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        visited = {}
        stack = [root]
        visited[root] = 1
        res = []
        
        is_leaf = lambda node: not node.left and not node.right
        
        while stack:
            top = stack[-1]
            if visited[top] == 2 or is_leaf(top):
                top = stack.pop()
                res.append(top.val)
            else: 
                if top.right:
                    stack.append(top.right)
                    visited[top.right] = 1
                if top.left:
                    stack.append(top.left)
                    visited[top.left] = 1
                visited[top] = 2
        return res

[Leetcode] 199. Binary Tree Right Side View

I referred to this solution: it's really succinct and ingenious. I am a little far from this level of coding.

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def rightSideView(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        def collect(node, depth):
            if not node:
                return
            if len(view) == depth:
                view.append(node.val)
            collect(node.right, depth+1)
            collect(node.left, depth+1)
        
        view = []
        collect(root, 0)
        return view

[Leetcode] 498. Diagonal Traverse

Well, this problem itself has nothing to note. But I must take a screen shot for record - the first time my program beats 100%... just for fun. Problem wise, it's just a bunch of index tricks - along the diagonal, element matrix[i][j], i + j maintains the same.

---

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

Note:

1. The total number of elements of the given matrix will not exceed 10,000.

---

One thing to note is that the input size says that we can only afford $O(n)$ algorithm.

class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not any(matrix): return []
        m, n = len(matrix), len(matrix[0])
        
        if m == 1: return matrix[0]
        if n == 1: return [matrix[i][0] for i in range(m)]
        
        res = []
        for k in range(m+n):
            if k >= n:
                start = k -n + 1 # row 
            else:
                start = 0
            if k >= m:
                end = m - 1 
            else:
                end = k
            tmp = []
            for i in range(start, end + 1):
                tmp.append(matrix[i][k-i])
            
            if k % 2 == 0:
                res += tmp[::-1]
            else:
                res += tmp
        return res
       

[Leetcode] 43. Multiply Strings

Looks like a simple problem. I thought to use Karatsuba algorithm to speed the program up, but it turns out not necessary - as the longest input will just be less than 180, then $O(180^2)$ is definitely good enough.

I briefly looked at some other people's hints and see that the key to this problem is that: num1[i] * num2[j] will be at final result's [i+j] position and [i+j+1] for the carrier.

---

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contains only digits 0-9.
3. Both num1 and num2 does not contain any leading zero.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

class Solution(object):
    def multiply(self, num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        n1, n2 = len(num1), len(num2)
        res = [0 for _ in range(n1+n2+1)]
        num1 = num1[::-1]
        num2 = num2[::-1]
        for i in range(n1):
            b1 = int(num1[i])
            for j in range(n2):
                b2 = int(num2[j])
                cur_b = res[i+j] + b1 * b2
                if cur_b <= 9:
                    res[i+j] = cur_b
                else:
                    res[i+j] = cur_b % 10
                    res[i+j+1] += cur_b / 10
        res = map(str, res)
        res = ''.join(res[::-1])
        i = 0
        while i < len(res) - 1 and res[i] == '0':
            i += 1
        return res[i:]

[MOOC] Deep Learning Specialization

I heard of this MOOC by Andrew Ng today and am really excited about it. As a huge fan of good MOOCs, I can't wait to try it out.

I long to systematically learn deep learning. I have applied some deep learning methods to some projects and achieved quite good results, and I am amazed by how well they work on certain problems and how easily they can transfer to a completely different task without much extra work.

With Keras package, building a decent neural network is probably just several lines of code, but it will be nice to gain some "correct" insights, especially from the best people in the field.

Speaking of this, I just love how open this field has been. Maybe I am not in the field, but I just feel amazed by how many good tutorials/MOOCs/software packages are out there. I think it definitely brings a better opportunity for whoever wants to study or work on it, but more importantly, as such an important technology that changes or will change people's life so much, these open resources allow people to see clearer what are causing the changes and be aware of them. This awareness, at least to myself, is important.

[Leetcode] Implement Trie (Prefix Tree)

Well, I just finished the week 1 of Algorithms on Strings. I think without doing homework problem there, I would not be able to think of how to represent the tree. BUT, of course, graph, adjacency list.

Implement a trie with insert, search, and startsWith methods.

class Trie(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.tree = {}
        self.tree[0] = {}
        self.new_node_idx = 1

    def insert(self, word):
        """
        Inserts a word into the trie.
        :type word: str
        :rtype: void
        """
        current_node = 0
        word = word + '$'
        for i in range(len(word)):
            current_symbol = word[i]
            if current_symbol in self.tree[current_node]:
                current_node = self.tree[current_node][current_symbol]
            else:
                self.tree[current_node][current_symbol] = self.new_node_idx
                self.tree[self.new_node_idx] = {}
                current_node = self.new_node_idx
                self.new_node_idx += 1

    def search(self, word):
        """
        Returns if the word is in the trie.
        :type word: str
        :rtype: bool
        """
        word = word + '$'
        current_node = 0
        for i in range(len(word)):
            current_symbol = word[i]
            if current_symbol in self.tree[current_node]:
                current_node = self.tree[current_node][current_symbol]
            else:
                return False
        return True
    
    def startsWith(self, prefix):
        """
        Returns if there is any word in the trie that starts with the given prefix.
        :type prefix: str
        :rtype: bool
        """
        current_node = 0
        for i in range(len(prefix)):
            cur_symbol = prefix[i]
            if cur_symbol in self.tree[current_node]:
                current_node = self.tree[current_node][cur_symbol]
            else:
                return False
        return True

# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)