czxttkl

https://leetcode.com/problems/insert-interval/

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[Interval]
        :type newInterval: Interval
        :rtype: List[Interval]
        """
        if not intervals:
            return [newInterval]
        strt_idx = self.binary_search(intervals, newInterval.start)        
        end_idx = self.binary_search(intervals, newInterval.end)
        
        if strt_idx ==0 and newInterval.end < intervals[0].start:    # Condition 1
            intervals[0:1] = [newInterval, intervals[0]]
        elif newInterval.start > intervals[strt_idx].end:            # Condition 2
            intervals[strt_idx:end_idx+1] = [intervals[strt_idx], 
                                             Interval(newInterval.start, max(intervals[end_idx].end, newInterval.end))]
        else:                                                        # Condition 3
            intervals[strt_idx:end_idx+1] = [Interval(min(intervals[strt_idx].start, newInterval.start), 
                                             max(intervals[end_idx].end, newInterval.end))]
        return intervals

    def binary_search(self, intervals, t):
        left, right = 0, len(intervals)-1
        while left <= right:
            mid = (left + right) / 2
            if t > intervals[mid].start:
                left = mid + 1
            elif t < intervals[mid].start:
                right = mid - 1
            else:
                return mid
        
        # return index where t >= intervals[index].start
        return left-1 if left - 1 >=0 else 0
        

Idea

Do two rounds of binary search to determine the rightmost interval in `intervals` whose start $latex \leq$ `newInterval.start`. Also determine the rightmost interval whose start $latex \leq$ `newInterval.end`. Then you have three situations to deal with:

https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/

Code

class Solution(object):
    def lengthOfLongestSubstringTwoDistinct(self, s):
        """
        :type s: str
        :rtype: int
        """
        end = dict()
        max_len = 0
        start = 0
        for i,c in enumerate(s):
            if len(end) <2:
                end = i
            else: # len(end) == 2
                if c in end.keys():
                    end = i
                else:
                    end_early_c = min(end.keys(), key=lambda x: end[x])
                    start = end[end_early_c] + 1
                    end.pop(end_early_c, None)
                    end = i
                
            l = i - start + 1
            if l > max_len:
                max_len = l
                
        return max_len

Idea

Use a dictionary `end` to record at which indices the previous two distinct characters are last seen. Then, when a new character appears which are not in `end.keys()`, the substring satisfying our rules can only start after one of the two existing characters, whichever is seen more earlier.

for example, `aaabbbaac`. When you see `c`, you can only start after `bb`.  

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

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 kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        for v in self.inorder(root):
            if k == 1:
                return v
            else:
                k -= 1
                
    def inorder(self, root):
        if root:
            for v in self.inorder(root.left):
                yield v
            yield root.val
            for v in self.inorder(root.right):
                yield v
        

Idea 

We use depth first in order traverse of BST to read element from the smallest to the largest. We can count when each element is read, until we read k element. Here we use `yield` instead of `return`  in the inorder function to be more memory thrifty. 

Locating the smallest element will take O(log N) time, plus you read O(k) element before you return.

Reference

https://leetcode.com/discuss/44731/pythonic-approach-with-generator

https://leetcode.com/problems/merge-intervals/

Code

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: List[Interval]
        """
        r = []
        for i in sorted(intervals, key=lambda x: x.start):
            if r and i.start <= r[-1].end:
                r[-1].end = max(i.end, r[-1].end)
            else:
                r += [i]
        return r
        

Idea

First, sort intervals based on their start points (Achieve in O(nlogn) time). Then, one by one examining whether the current start point is behind or in front of the last effective interval’s end point. The following plot shows the specific rules for update:

https://leetcode.com/problems/summary-ranges/

class Solution(object):
    def summaryRanges(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        res = []
        s = ""
        for i, v in enumerate(nums):
            if i == 0:
                s = str(v)
            else:
                if nums[i-1] == nums[i] - 1:
                    s = s.split("->")[0] + "->" + str(nums[i])
                else:
                    res.append(s)
                    s = str(nums[i])
                    
        if s:
            res.append(s) 

        return res    

Idea:

Nothing too much.

https://leetcode.com/problems/unique-word-abbreviation/

a) it                      --> it    (no abbreviation)

     1
b) d|o|g                   --> d1g

              1    1  1
     1---5----0----5--8
c) i|nternationalizatio|n  --> i18n

              1
     1---5----0
d) l|ocalizatio|n          --> l10n

Given dictionary = [ "deer", "door", "cake", "card" ]

isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

class ValidWordAbbr(object):
    def __init__(self, dictionary):
        """
        initialize your data structure here.
        :type dictionary: List[str]
        """
        self.c2k = lambda s: s[0] + str(len(s)-2) + s[-1]
        ab = [(self.c2k(s), s) for s in dictionary]
        d = dict()
        for k,v in ab:
            if not d.get(k):
                d[k] = set()
            d[k].add(v)
        self.d = d


    def isUnique(self, word):
        """
        check if a word is unique.
        :type word: str
        :rtype: bool
        """
        key = self.c2k(word)
        if not self.d.get(key):
            return True
        else:
            if word in self.d[key] and len(self.d[key])==1:
                return True
        
        return False
        


# Your ValidWordAbbr object will be instantiated and called as such:
# vwa = ValidWordAbbr(dictionary)
# vwa.isUnique("word")
# vwa.isUnique("anotherWord")

https://leetcode.com/problems/valid-parentheses/

Valid Parentheses

My code:

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stk = []
        def peek():
            return stk[-1] if len(stk) > 0 else None
        
        for k in s:
            if k == ")":
                if peek() == "(":
                    stk.pop()
                else:
                    return False
            elif k == "]": 
                if peek() == "[":
                    stk.pop()
                else:
                    return False
            elif k == "}": 
                if peek() == "{":
                    stk.pop()
                else:
                    return False
            else:
                stk.append(k)     
            
        return stk == []
        

More elegant (Ref: https://leetcode.com/discuss/19900/simple-python-solution-with-stack):

class Solution:
    # @return a boolean
    def isValid(self, s):
        stack = []
        dict = {"]":"[", "}":"{", ")":"("}
        for char in s:
            if char in dict.values():
                stack.append(char)
            elif char in dict.keys():
                if stack == [] or dict[char] != stack.pop():
                    return False
            else:
                # Other invalid characters 
                return False
        return stack == []

Idea:

Stack will be empty if the string is valid. When you meet “)”, “]” or “}”, you check if the first element in stack is “(“, “[” or “{” correspondingly.

Code

class Solution(object):
    # For reference, this is Word Break I problem: https://czxttkl.com/?p=930
    def wordBreak1(self, s, words):
        d = [False] * len(s)    
        for i in range(len(s)):
            for w in words:
                if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1):
                    d[i] = True
        return d[-1]
    
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        # To pass a test case, I need to first check a word is breakable or not. 
        # We don't need this actually.
        if not self.wordBreak1(s, wordDict):
            return []
        self.res = []
        self.words = set(wordDict)
        self.helper(s, "")
        return self.res
        
    def helper(self, s, concat):
        for i in xrange(1, len(s)+1):
            if s[0:i] in self.words:
                concat_cp = concat + ' ' + s[0:i]
                if i == len(s):
                    # strip to remove first ' '
                    self.res += [concat_cp[1:]]
                else:
                    self.helper(s[i:], concat_cp)
                    
                    

Idea:

DFS essentially. The time complexity is O(3^N), where N is the length of s. How to get this time complexity?

T(1)=T(1)

T(2)=(T(1)+T(1))+T(1) = 3T(1)     # Check if the first character and the second character are words in the dictionary, or check    
                                  # if the whole two characters form a word in the dictionary

T(3) = (T(1)+T(2))+(T(2)+T(1))+T(1) # Check if the first character and the last two characters are words in the dictionary, or 
                                    # check if the first two characters and the last character are words in the dictionary, or 
                                    # check if the whole three characters form a word in the dictionary. 
...
T(N) = (T(1)+T(N-1))+(T(2)+T(N-2))+...+(T(N-1)+T(1))+T(1)
     = 3T(N-1)

Since the time complexity is exponential, leetcode doesn’t pass my code for certain test cases. I added the function from Word Break I to first check if a word is breakable. If yes, then I continue to generate return strings. In this way I passed the leetcode OJ.

To alleviate the duplication of computation, we can use dynamic programming idea to have more space in trade of the time. But I don’t think it can alleviate the time complexity of the worst case.

Code (https://leetcode.com/discuss/64513/python-dp-solution-in-11-lines):

def wordBreak(self, s, wordDict):
    """
    :type s: str
    :type wordDict: Set[str]
    :rtype: List[str]
    """
    M = {}
    def dfs(remain_str):
        if not remain_str: return ['']
        if remain_str in M: return M[remain_str]
        ret = []    
        for i in xrange(1,len(remain_str)+1):
            if remain_str[:i] in wordDict: 
                for r in dfs(remain_str[i:]): 
                    ret.append( (remain_str[:i]+' '+r).strip() )
        M[remain_str] = tuple(ret)
        return ret
    return dfs(s)

https://leetcode.com/problems/word-break/

DP Idea

You create a boolean array `f` of length `len(s)+1`. “`f[i] == True`” means substring `s[0:i-1]` can be matched successfully.

Jave code (Ref: https://leetcode.com/discuss/18904/java-implementation-using-dp-in-two-ways): 

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {

        boolean[] f = new boolean[s.length() + 1];
        Arrays.fill(f, false);

        f[0] = true;

        //Second DP
        for(int i=1; i <= s.length(); i++){
            for(int j=0; j < i; j++){
                if(f[j] && dict.contains(s.substring(j, i))){
                    f[i] = true;
                    break;
                }
            }
        }

        return f[s.length()];
    }
}

This algorithm takes O(N^2) time complexity and O(N) space.

Python Code Using DP (Ref: https://leetcode.com/discuss/23605/simple-dp-solution-in-python-with-description)

def word_break(s, words):
    d = [False] * len(s)    
    for i in range(len(s)):
        for w in words:
            if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1):
                d[i] = True
    return d[-1]

This algorithm improves the time complexity to O(NK) but still uses O(N) space.

Another improved Python Code

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
  
        break_idx = []
        for i in xrange(len(s)):
            if s[0:i+1] in wordDict:
                break_idx.append(i)
            else:
                for b in break_idx:
                    if s[b+1:i+1] in wordDict:
                        break_idx.append(i)
                        break
        
        return len(break_idx)>0 and break_idx[-1]== len(s)-1

This algorithm works better if you know there are only a few positions in `s` that can be segmented into words. (i.e., you know d[i]==True for only a small number of i, in the previous algorithm)

BFS Idea:

https://leetcode.com/discuss/8479/a-solution-using-bfs

But it is essentially similar to the DP idea. The time complexity is O(N^2).

Code

from collections import deque

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        l = deque([0])
        visited = set()
        while l:
            n = l.popleft()
            for word in wordDict:
                start = n
                end = start + len(word)
                if s[start:end] == word and end not in visited:
                    if end == len(s):
                        return True
                    l.append(end)
                    visited.add(end)
        
        return False

You can also use Trie (prefix tree) to solve this problem. (TODO)