czxttkl

https://leetcode.com/problems/merge-k-sorted-lists/

Code 1:

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

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        dummy = ListNode(-1)
        cur = dummy
        if not lists:
            return None

        h = [(lists[i].val, lists[i]) for i in xrange(len(lists)) if lists[i] ]

        heapq.heapify(h)

        while len(h) > 0:
            t = heapq.heappop(h)
            cur.next = t[1]
            cur = cur.next
            if t[1].next:
                heapq.heappush(h, (t[1].next.val, t[1].next)) 

        return dummy.next

Use a min-heap to store k lists’ heads. Build a heap requires O(k) time. Every time you pop the least value from the heap, and push into that value’s next node into the heap. Since there are N elements in total and each heap push takes O(logK) time, the algorithm takes O(K+NlogK) time (O(K) is for heapify) but also O(K) additional space.

See [1] and [2] why the time complexity of heapify is O(K).

[1] http://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity

[2] https://www.cs.bgu.ac.il/~ds122/wiki.files/Presentation09.pdf

Code 2:

Use O(NlogK) time and there is no additional space required. Everytime you merge k/2 pairs lists. Reference: https://leetcode.com/discuss/20774/sharing-straightforward-solution-without-structure-vector

class Solution {
public:
    ListNode *mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (NULL == l1) return l2;
        else if (NULL == l2) return l1;
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.empty()) return NULL;
        int len = lists.size();
        while (len > 1) {
            for (int i = 0; i < len / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[len - 1 - i]);
            }
            len = (len + 1) / 2;
        }

        return lists.front();
    }
};

Similar Idea using Java:

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode head=null;
        ListNode former=null;
        while (l1!=null&&l2!=null) {
            if (l1.val>l2.val) {
                if (former==null) former=l2; else former.next=l2;
                if (head==null) head=former; else former=former.next;
                l2=l2.next;
            } else {
                if (former==null) former=l1; else former.next=l1;
                if (head==null) head=former; else former=former.next;
                l1=l1.next;
            }
        }
        if (l2!=null) l1=l2;
        former.next=l1;
        return head;

    }

    public ListNode mergeKLists(List<ListNode> lists) {
        if (lists.size()==0) return null;
        if (lists.size()==1) return lists.get(0);
        if (lists.size()==2) return mergeTwoLists(lists.get(0), lists.get(1));
        return mergeTwoLists(mergeKLists(lists.subList(0, lists.size()/2)), 
            mergeKLists(lists.subList(lists.size()/2, lists.size())));
    }
}

https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue

Reference:

[
  "wrt",
  "wrf",
  "er",
  "ett",
  "rftt"
]

Code

from sets import Set

class Solution(object):
    def alienOrder(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        if not words:
            return ""

        if len(words) == 1:
            return "".join([s for s in Set(words[0])])

        # len(words) >=2
        adj_dict = self.build_graph(words)
        visit_dict = dict([(k,0) for k in adj_dict.keys()])
        res = []
        self.valid = True
        
        for c in adj_dict.keys():
            self.topo_sort(c, visit_dict, adj_dict, res)
        return "".join([s for s in res]) if self.valid else ""

    def build_graph(self, words):
        adj_dict = {}

        def add_node(c):
            if adj_dict.get(c, None) == None:
                adj_dict = {}

        def add_link(src, des):
            adj_dict[src][des] = None

        for i in xrange(len(words)-1):
            w1 = words[i]
            w2 = words[i+1]
            start2 = 0
            for j in xrange(min(len(w1), len(w2))):
                if w1[j] == w2[j]:
                    add_node(w1[j])
                else:
                    add_node(w1[j])
                    add_node(w2[j])
                    add_link(w2[j], w1[j]) 
                    start2 = j+1
                    break   
            for j in xrange(start2, len(w1)):
                add_node(w1[j])             
            for j in xrange(start2, len(w2)):
                add_node(w2[j])
                
        return adj_dict

    def topo_sort(self, c, visit_dict, adj_dict, res):
        if self.valid and not visit_dict:
            visit_dict = 1
            for adj_c in adj_dict.keys():
                if visit_dict[adj_c] == 1:
                    self.valid = False
                    return
                if not visit_dict[adj_c] and self.valid:
                    self.topo_sort(adj_c, visit_dict, adj_dict, res)
            
            visit_dict = 2
            res.append(c)
        
                

Idea

Build a graph first, in which nodes are letters and a link from letter A to letter B means A should be latter than B in the final order. Then use topological sort to output nodes in order. https://en.wikipedia.org/wiki/Topological_sorting

https://leetcode.com/problems/lru-cache/

class Node(object):
    def __init__(self, val, key=None):
        self._prev = None
        self._next = None
        self._val = val
        self._key = key
    
    @property
    def val(self):
        return self._val
    
    @val.setter
    def val(self, value):
        self._val = value
        
    @property
    def key(self):
        return self._key

    @property
    def prev(self):
        return self._prev 

    @prev.setter
    def prev(self, node):
        self._prev = node     
   
    @property
    def next(self):
        return self._next

    @next.setter
    def next(self, node):
        self._next = node

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity
        self.table = {}
        self.dummy_head = Node(-1)
        self.dummy_tail = Node(-1)
        self.dummy_head.next = self.dummy_tail
        self.dummy_tail.prev = self.dummy_head

    def get(self, key):
        """
        :rtype: int
        """
        if self.table.get(key, None):
            node = self.table.get(key)
            self.del_node(node)
            self.tail_node(node)
            return node.val
        else:
            return -1

    def set(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: nothing
        """
        if self.table.get(key, None):
            node = self.table.get(key)
            node.val = value
            self.del_node(node)
            self.tail_node(node)            
        else:
            node = Node(value, key)
            self.table[key] = node
            self.tail_node(node)

            if len(self.table) > self.capacity: 
                node_del = self.dummy_head.next
                self.del_node(node_del)
                self.table.pop(node_del.key, None)

    def del_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def tail_node(self, node):
        node.prev = self.dummy_tail.prev
        node.next = self.dummy_tail
        self.dummy_tail.prev.next = node
        self.dummy_tail.prev = node

    
        

Idea:

First, we want to create a double linked list storing caches. Using this data structure, we can insert and delete cache in O(1) time. To be more convenient, we have a dummy head and dummy tail at the beginning and the end of the double linked list. All caches will be inserted between dummy_head and dummy_tail. The cache closer to dummy_head is less recently used. The cache closer to dummy_tail is more recently used. In `LRU`, we also have a `self.table` hash table to record key-node mapping.

Now, when you set a cache, you check whether it is stored in the double linked list before. If it is (line 67), we update its value. Then we remove it from the double linked list temporarily and then add it to the tail. If the cache is not stored before, you have to add its key to self.table as well as add it to the tail. However, this may cause the cache size overflow. To deal with it, you need to remove the next element dummy_head points to.

A caveat is that `get` function will not simply return a cache’s value but also needs to put that cache to the tail of the double linked list (line 55-56).

Reference:

https://leetcode.com/discuss/20139/java-hashtable-double-linked-list-with-touch-of-pseudo-nodes

https://leetcode.com/problems/encode-and-decode-strings/

string encode(vector<string> strs) {
  // ... your code
  return encoded_string;
}

vector<string> decode(string s) {
  //... your code
  return strs;
}

string encoded_string = encode(strs);

vector<string> strs2 = decode(encoded_string);

Code:

class Codec:
    def encode(self, strs): 
        return ''.join(s.replace('|', '||') + ' | ' for s in strs) 
    def decode(self, s): 
        return [t.replace('||', '|') for t in s.split(' | ')[:-1]]

Idea:

Use ” | ” as a delimiter of strings. If any string has “|” in it, you need to replace it with “||” in advance. When decoding, you first get ” | ” splitted words. Then, if there is any “||” in splitted words, you need to replace it back with “|”. Don’t forget to exclude the last element of `s.split(‘ | ‘)` since it is an empty string. 

Reference:

https://leetcode.com/discuss/54910/1-liners-ruby-python

https://leetcode.com/problems/3sum/

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Code

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums or len(nums) < 3:
            return []
            
        res = []
        nums.sort()
        
        for i in xrange(len(nums)-2):
            if i > 0 and nums[i-1] == nums[i]:
                continue
            
            target = -nums[i]
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if nums[left] + nums[right] == target:
                    res.append([nums[i], nums[left], nums[right]])
                    left_val = nums[left]
                    right_val = nums[right]
                    left += 1
                    right -= 1
                    while left < right and nums[left]==left_val:
                        left += 1
                    while right > left and nums[right]==right_val:
                        right -= 1
                elif nums[left] + nums[right] < target:
                    left = left + 1
                else:
                    right = right - 1
                    
        return res
                

Idea:

You sort the array first in O(nlogn) time. Then you have a pointer `i` starting from 0 and ending at len(nums)-3. The number pointed by `i` denotes the candidate for the first number in a 3sum triplet. You want to run a 2sums algorithm on all elements on the right of `i` with target equal to `-nums[i]`: you create a `left` pointer right next to `i` and a `right` pointer at the end of nums. You move `left` to right or move `right` to left according to `nums[left] + nums[right] ? target`. You should take care of duplication, either for `i` (line 14 -15) and for `left` and `right` (line 27-30)

The time complexity is O(N^2) and space complexity is O(1).

Reference:

Code:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dict = {}
        for idx, vlu in enumerate(nums):
            idx2 = dict.get(target - vlu, -1)
            if idx2 < 0:
                dict[vlu] = idx
            else:
                return [idx2+1, idx+1]

Idea:

O(N) space. O(N) time. Read my another post on 3Sum, which sorts array in place in O(nlogn) time but costs no additional space. (3Sum algorithm takes O(N^2) overall)

UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

https://leetcode.com/problems/search-in-rotated-sorted-array/

Code

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        
        left, right = 0, len(nums)-1                    
        while left <= right:
            mid = (left + right) / 2
            if nums[mid] == target:
                return mid
            if nums[left] <=nums[mid]:
            # left ok
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
            # right ok
                if nums[right] >= target > nums[mid]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1

Idea

It is a variant of binary search. You have `left`, `right` and `mid` three pointers. You only return exact index of `mid` if you find `nums[mid] == target`. Otherwises you return -1. To identify whether you need to search in `[left, mid-1]` or `[mid+1, right]`, you need to determine `nums[left] <= nums[mid]` (line 16). If it is True, that means `nums[left:mid]` is intact from rotation. If it is  False, that means `nums[mid+1:right]` is intact by rotation. Then you determine you need to search in the intact part of the rotated part (line 18 and 24).

Reference:

https://leetcode.com/problems/closest-binary-search-tree-value-ii/

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 closestKValues(self, root, target, k):
        """
        :type root: TreeNode
        :type target: float
        :type k: int
        :rtype: List[int]
        """
        stk1 = []
        stk2 = []
        self.inorder(root, False, target, stk1)
        self.inorder(root, True, target, stk2)
        
        res = []
        for _ in xrange(k):
            if not stk1:
                res.append(stk2.pop())
            elif not stk2:
                res.append(stk1.pop())
            else:
                if abs(stk1[len(stk1)-1] - target) < abs(stk2[len(stk2)-1] - target):
                    res.append(stk1.pop())
                else:
                    res.append(stk2.pop())
        return res
        
    def inorder(self, root, reverse, target, stk):
        if root is None:
            return 
        self.inorder(root.right, reverse, target, stk) if reverse else self.inorder(root.left, reverse, target, stk)
        # The first inequality is less than or equal, the second inequality must be larger than (without equal).
        # Or the first is less than, the second is larger than or equal to
        if not reverse and target <= root.val:
            return
        if reverse and target > root.val:
            return
        stk.append(root.val)
        self.inorder(root.left, reverse, target, stk) if reverse else self.inorder(root.right, reverse, target, stk)

        

Idea:

If we do inorder depth-first traverse (left->root->right) of a binary search tree, we can get an ascending sorted list of elements. If we do reverse inorder depth-first traverse (right->root->left) of a binary search tree, we can get a descending sorted list.

So we create two stacks to store. Stack 1 records the ascending sorted list but it terminates before the element which <= target. (line 40). Stack 2 records the descending sorted list but it terminates at the element which < target. (line 42). (You can also make the first inequality with less than, and the second inequality with larger than or equal to. The main point is that the two stacks shouldn’t contain any element at the same time.)

At last you peek at stack 1 and stack 2. You need to pop element into `res` list from whichever stack has the top element closer to target.

Reference:

https://leetcode.com/discuss/55240/ac-clean-java-solution-using-two-stacks

https://leetcode.com/problems/regular-expression-matching/

'.' Matches any single character.
'*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true

Code 1:

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if p == "":
            return s == ""
        
        if len(p)>=2 and p[1] == "*":
            return  s != "" and (s[0] == p[0] or p[0] == ".") and self.isMatch(s[1:], p) or self.isMatch(s, p[2:])         
        else:
            return s != "" and (s[0] == p[0] or p[0] == ".") and self.isMatch(s[1:], p[1:])

Reference: http://xiaohuiliucuriosity.blogspot.com/2014/12/regular-expression-matching.html

Idea:

This is a recursive method.  You start to “consume” `p` and `s` until `p` can be consumed to empty.  If at this moment `s` happens to be consumed to empty also, your match is successful.

Everytime you look at the first and the second character in `p`. There are two situations:

If you find the second character in `p` is “*”. This means, on the left of “*” in p, there is another character, `x`, for example:

p:   x*......

s:   ...............

Then, there are three conditions:

a) `x` is not `.` and the first position of `s` is not the same as `x`. Then you must skip `x*` in p to  continue to match `s`.  So you rely on `isMatch(s, p[2:])`.

b) `x` is not `.` and the first position of `s` is the same as `x`. Then whether `p` matches `s` will depend on ‘isMatch(s[1:], p)’ or `isMatch(s, p[2:])`. You can imagine that the following match will continue to try if the `s`’s following substring  starts with `x*`. 

c) `x` is `.`. Then whether `p` matches `s` will also depend on `isMatch(s[1:], p)`

If you find the second character in `p` is not “*”, then a successful match will only happen if the first character of `p` and `s` are the same and `isMatch(s[1:], p[1:])`, i.e., the rest of `p` and `s` match.

The most bottom case of `isMatch` will only return True when `p` is empty and `s` is empty also. This means `s` has all been matched by `p` without anything left unmatched. Notice that line 12 and line 14 will return False immediately if `s` is empty. This means there are something left in `p` but you have consumed all `s`.

However, this method can’t pass Leetcode OJ written in Python. The time complexity is large because you are essentially exhausting all possible situations. Naturally, you can convert such algorithm into DP.

Code 2:

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        table = [[False] * (len(s)+1) for _ in xrange(len(p)+1)]
        table[0][0] = True
        for i in xrange(2, len(p)+1):
            table[i][0] = p[i-1] == '*' and table[i-2][0]
            
        for i in xrange(1, len(p)+1):
            for j in xrange(1, len(s)+1):
                if p[i-1] == '*':
                    table[i][j] = (p[i-2] == '.' or p[i-2] == s[j-1]) and table[i][j-1] or table[i-2][j]
                else:
                    table[i][j] = (p[i-1] == '.' or p[i-1] == s[j-1]) and table[i-1][j-1]


        return table[-1][-1]

Reference: https://leetcode.com/discuss/55253/my-dp-approach-in-python-with-comments-and-unittest

Idea:

It is a DP algorithm. table[i][j] records whether p[0:i] matches s[0:j]. table[0][0] is True because “” matches “”. table[i][0] is the result of a pattern matching “”. It will only be true if `p` only contains `x*` pattern. table[0][j] will always be False because an empty pattern will not be able to match any string. 

Then, we start to update table[i][j], column first.

If p[i-1] == “*”, table[i][j] will be true if:

1. p[i-1] equals to s[j-1] and p[0:i] matches s[0:j-1] (str1 + “x*” matches str2 => str1 + “x*” matches str2 + “x”),
2. p[0:i-1] matches s[0:j] (str1 matches str2 => str1+”x*” matches str2) 

if p[i-1] is not “*”, table[i][j] will be true if p[0:i-1] matches s[0:j-1] (str1 matches str2 => str1+”x” matches str2+”x”)

This algorithm uses O(|p||s|) space to get fast running time. It is accepted by Leetcode finally.