czxttkl

https://leetcode.com/problems/scramble-string/

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

 

Code

class Solution(object):
    def isScramble(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) != len(s2):
            return False
        elif not s1:
            return True
        
        n = len(s1)
        res = [[[False for _ in xrange(n)] for _ in xrange(n)] for _ in xrange(n+1)]  # the size of the first dim is n+1
                                                                                      # easy for indexing
        for j in xrange(n):
            for m in xrange(n):
                res[1][j][m] = (s1[j] == s2[m])
            
        for i in xrange(2, n+1):
            for j in xrange(n-i+1):
                for m in xrange(n-i+1):
                    for k in xrange(1,i):
                        res[i][j][m] |= (res[k][j][m] and res[i-k][j+k][m+k]) \
                                        or (res[k][j][m+i-k] and res[i-k][j+k][m])
                        
        return res[n][0][0]

 

Idea

See here: http://tianmaying.com/tutorial/LC87

One note is that we put for i in xrange(2, n+1)  at the outmost loop (line 20), where `i` is the length of the two substrings, `s1[j:j+i] and s2[m:m+i]`, under comparison. When we calculate `res[i][j][m]`, we always need some `res[k’][j’][m’]` where `k’ < i`. Therefore, we need to calculate `res` in ascending order of `i`, the first dimension of `res`.

https://leetcode.com/problems/insertion-sort-list/

Sort a linked list using insertion sort.

 

Code 

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = ListNode(0)
        cur = head
        while cur:
            isrt = new_head
            next = cur.next
            
            while isrt.next and isrt.next.val < cur.val:
                isrt = isrt.next
            
            cur.next = isrt.next
            isrt.next = cur
            cur = next
            
        return new_head
            

 

Idea

By definition, insertion sort is inserting each element to the current sorted array by comparing it to the elements in the current sorted array. It requires O(N^2) time asymptotically. In my code, `isrt` is used to locate the correct position to insert the new element. It is set to the head every time a new element needs to be inserted (Line 16).  

However, the code above can’t pass the leetcode OJ. One way to circumvent it is to set `isrt` more passively (set `isrt` only when very necessary) instead of setting it to head for every new element to be inserted.

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        new_head = ListNode(0)
        cur = head
        isrt = new_head
        
        while cur:
            next = cur.next
            
            if not isrt or not isrt.next or isrt.next.val>=cur.val:
                isrt = new_head
            
            while isrt.next and isrt.next.val < cur.val:
                isrt = isrt.next
            
            cur.next = isrt.next
            isrt.next = cur
            cur = next
            
            
        return new_head.next

 

https://leetcode.com/problems/zigzag-conversion/

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P   A   H   N
A P L S I I G
Y   I   R

And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

 

Code

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if s is None or len(s) <= numRows or numRows==1:
            return s
        
        res = ""
        for i in xrange(numRows):
            if i == 0 or i == (numRows-1):
                res += s[i::(2*numRows-2)]
            else:
                s1 = s[i::(2*numRows-2)]
                s2 = s[(2*numRows-2-i)::(2*numRows-2)]
                for c1, c2 in zip(s1, s2):
                    res += c1 + c2
                if len(s1) > len(s2):  # s1 is at most longer than s2 by one character
                    res += s1[-1]
        return res
                    
                    

 

Idea

Every `2*numRows-2` characters in `s` will form one zigzag. You can find the rules when outputing the zigzag horizontally:

https://leetcode.com/problems/maximum-gap/

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

 

Code

import sys
import math

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums or len(nums) < 2:
            return 0
        
        # find max and min in nums
        max_num = -sys.maxint
        min_num = sys.maxint
        for i in nums:
            if i > max_num:
                max_num = i
            if i < min_num:
                min_num = i
        
        if max_num == min_num:
            return 0
        
        bucket_max = [None for _ in xrange(len(nums)+2)]  
        bucket_min = [None for _ in xrange(len(nums)+2)] 
        for i in nums:
            # max_num is actually assigned to n+2-th bucket  
            bucket = ((i-min_num) * (len(nums)+1)) / (max_num - min_num)  
            bucket_max[bucket] = max(bucket_max[bucket], i) if bucket_max[bucket] is not None else i
            bucket_min[bucket] = min(bucket_min[bucket], i) if bucket_min[bucket] is not None else i
        
        max_gap = 0
        prev_max = bucket_max[0]       # the first bucket must have one element
        for i in xrange(1, len(bucket_min)):
            if bucket_min[i] is not None:
                max_gap = max(bucket_min[i] - prev_max, max_gap)
                prev_max = bucket_max[i]
            
        return max_gap

 

Idea

This is a problem using the classic ideas of bucketing and pigeon hole principle. The logic is that, we create `n+1` buckets between `max_num` and `min_num`, where `max_num` and `min_num` of the array can be found in O(N) time. Since there are only `n` numbers in the array, there must be at least one bucket without any number landing in it. This important factor indicates that the max distance of two consecutive numbers in the sorted form must happen between the maximal number in one previous bucket and the minimal number in one latter bucket and the two buckets have at least one empty bucket between them. Any numbers falling into the same bucket will not have the difference exceeding the bucket range, which is `(max_num-min_num)/(n+1)`. 

https://leetcode.com/problems/simplify-path/

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

click to show corner cases.

Code

class Solution(object):
    def simplifyPath(self, path):
        """
        :type path: str
        :rtype: str
        """
        paths = path.split("/")
        fs = []
        for p in paths:
            if p == "..":
                # when fs is empty, ".." has no effect
                if fs:
                    fs.pop()
            elif p == ".":
                pass
            elif p == "":
                pass
            else:
                fs.append(p)
        return "/" + "/".join(fs)
                
        

 

Idea

Since there could be “..” (the up level folder) and “.” (the current folder) in the path, it is natural to maintain a stack to record  folder hierarchy. The crux of this problem is to consider all possible corner cases, such as paths with two or more consecutive backslashes, or paths ending with backslashes, or paths already landing in “/” but with more “..” followed.  

https://leetcode.com/problems/gray-code/

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0
01 - 1
11 - 3
10 - 2

Note:
For a given n, a gray code sequence is not uniquely defined.

For example, [0,2,3,1] is also a valid gray code sequence according to the above definition.

For now, the judge is able to judge based on one instance of gray code sequence. Sorry about that.

 

Code

class Solution(object):
    def grayCode(self, n):
        """
        :type n: int
        :rtype: List[int]
        """
        if n<0:
            return []
        
        res = [0]
        for i in xrange(n):
            for j in xrange(len(res)-1, -1, -1):
                res.append(res[j] + (1 << i))
        return res

 

Idea

Say we have already had the gray codes for n. Then, the gray codes for n+1 are constituted from:

1. ‘0’ followed by the gray codes for n
2. ‘1’ followed by the gray codes for n in the reversed order

 

https://leetcode.com/problems/unique-binary-search-trees-ii/

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

 

Code

# 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 copy(self, root, bias):
        if not root:
            return root
        
        new_root = TreeNode(root.val + bias)
        new_root.left = self.copy(root.left, bias)
        new_root.right = self.copy(root.right, bias)
        return new_root
        
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
            
        ans = [[] for _ in xrange(n+1)]
        ans[0] = [None]
        
        for i in xrange(1, n+1):
            for j in xrange(1, i+1):    # j is the root value
                for lt in ans[j-1]:
                    for rt in ans[i-j]:
                        root = TreeNode(j)
                        root.left = self.copy(lt, 0)
                        root.right = self.copy(rt, j)
                        ans[i] += [root]
        return ans[-1]

 

Idea

To extend the idea of Leetcode 96, when you are given `n`, you can put `1~n` as roots. When you put `i` (`1<=i<=n`) as the root, the left tree is depending on the result of `i-1` and the right tree is depending on the result of `n-i`. For this problem, the right tree is not solely copy of the trees of `n-i`. Every node in the trees of `n-i` should be added a bias of `i`. Therefore, we create a recursive function `copy(self, root, bias)` to copy trees with biases. 

https://leetcode.com/problems/unique-binary-search-trees/

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

 

Code

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if not n:
            return 0
            
        numOfTrees = [0] * (n+1)     # for easier indexing. Using numOfTrees[1:]
        numOfTrees[0] = 1
        
        for i in xrange(1, n+1):
            for j in xrange(1, i+1):
                numOfTrees[i] += numOfTrees[j-1] * numOfTrees[i-j] 
            
        return numOfTrees[n]

 

Idea

When you are given `n` (`n` is the size of sorted numbers to be placed in BST), there are multiple ways to construct unique BSTs depending on which element is placed as the root: you can put the first element as the root, then place the remaining `n-1` elements in the right tree. You can put the second element as the root, then place the first element as the left tree and the remaining `n-2` elements in the right tree. So on and so forth. 

Therefore, you can use an array, `numOfTrees` in my code, to store the number of unique BSTs. The final result, `numOfTrees[n]`, will be based on `numOfTrees[n’]` where `n’ < n`: You can put 1~n as root. When you put element `i` (`1<=i<=n`) as the root, its left tree can have `numOfTrees[i-1]` different unique ways of construction and its right tree can have `numOfTrees[n-i]` ways of construction. So the total number of unique trees when root equal to `i` is `numOfTrees[i-1] *numOfTrees[n-i]`.

A more mathematical way is to directly solve this problem using Catalan Number. Then you only need O(N) time and O(1) space. Please find introduction to Catalan Number below:

catalan 

https://leetcode.com/problems/interleaving-string/

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

For example,
Given:
s1 = "aabcc",
s2 = "dbbca",

When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

 

Code

class Solution(object):
    def isInterleave(self, s1, s2, s3):
        """
        :type s1: str
        :type s2: str
        :type s3: str
        :rtype: bool
        """
        if len(s1) + len(s2) != len(s3):
            return False
        if not s1:
            return s3 == s2
        if not s2:
            return s3 == s1
        
        res = [[False] * (len(s1)+1) for _ in xrange(len(s2)+1)]
        
        for i in xrange(len(s1)+1):
            res[0][i] = (s1[:i] == s3[:i])
        for j in xrange(len(s2)+1):
            res[j][0] = (s2[:j] == s3[:j])
        
        for j in xrange(1, len(s2)+1):
            for i in xrange(1, len(s1)+1):
                res[j][i] = (res[j][i-1] and (s3[i+j-1] == s1[i-1])) or (res[j-1][i] and (s3[i+j-1]==s2[j-1]))
        
        return res[-1][-1]
        

 

Idea

Use DP. `res[j][i]` is the boolean indicator of whether `s3[:i+j]` is an interleaving string of `s1[:i]` and `s2[:j]`. It can be written recursively as `res[j][i] = (res[j][i-1] and (s3[i+j-1] == s1[i-1])) or (res[j-1][i] and (s3[i+j-1]==s2[j-1]))`. 

 

Reference

http://tianmaying.com/tutorial/LC97

https://leetcode.com/problems/symmetric-tree/

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

 

Code

# 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 isSymmetric(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return not root or self.dfs(root.left, root.right)
        
    def dfs(self, root1, root2):
        if (not root1 and root2) or (not root2 and root1):
            return False
        elif not root1 and not root2:
            return True
        elif root1.val == root2.val:
            return self.dfs(root1.left, root2.right) and self.dfs(root1.right, root2.left)
        else:
            return False

 

Idea

Maintain two pointers pointing to symmetric positions in the tree. If the two tree nodes being pointed to are not None and have same value, then recursively check if their children in the symmetric positions are the same. If the two tree nodes being pointed to are both None, it also indicates they are symmetric.