czxttkl

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Code

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        
        # convert to integer matrix
        for i in xrange(len(matrix)):
            for j in xrange(len(matrix[0])):
                matrix[i][j] = int(matrix[i][j])
            
        max_size = max(matrix[0])
        # DP storage initialized with the first row of matrix
        vec = list(matrix[0])
        
        for row in xrange(1, len(matrix)):
            topleft = vec[0]
            vec[0] = matrix[row][0]
            
            for col in xrange(1, len(matrix[0])):
                if matrix[row][col] == 0:
                    new = 0
                else:
                    new = min(topleft, vec[col-1], vec[col]) + 1
                topleft = vec[col]
                vec[col] = new
            
            max_size = max(max_size, max(vec))
                
        return max_size * max_size
        
        
        

Idea

Think about it as a 2D DP problem. Suppose a list vec has size num_row * num_col. vec[i][j] is the size of the maximum square that can be achieved at matrix[i][j]. The core logic is that vec[i][j] = min(vec[i][j-1], vec[i-1][j],vec[i-1][j-1]). 

And we know that 2D DP problem can often be reduced to 1D. That’s how I implement currently.

Reference:

https://discuss.leetcode.com/topic/15328/easy-dp-solution-in-c-with-detailed-explanations-8ms-o-n-2-time-and-o-n-space

void addWord(word)
bool search(word)

addWord("bad")
addWord("dad")
addWord("mad")
search("pad") -> false
search("bad") -> true
search(".ad") -> true
search("b..") -> true

Code

class TrieNode():
    def __init__(self):
        self.nodes = {}
        self.isword = False
    
class WordDictionary(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.root = TrieNode()

    def addWord(self, word):
        """
        Adds a word into the data structure.
        :type word: str
        :rtype: void
        """
        root = self.root
        for i, ch in enumerate(word):
            if not root.nodes.get(ch, None):
                root.nodes[ch] = TrieNode()
            root = root.nodes[ch]
            if i == len(word) - 1:
                root.isword = True

    def search(self, word):
        """
        Returns if the word is in the data structure. A word could
        contain the dot character '.' to represent any one letter.
        :type word: str
        :rtype: bool
        """
        assert len(word) > 0
        return self.search_helper(word, 0, self.root)
        
    def search_helper(self, word, idx, root):
        ch = word[idx]
        if ch == '.':
            if idx == len(word) - 1:
                 return any(map(lambda x: x.isword, root.nodes.values()))
            else:
                 return any(map(lambda x: self.search_helper(word, idx+1, x), root.nodes.values()))
        else:
            if root.nodes.get(ch, None) is None:
                return False
            else:
                if idx == len(word) - 1:
                    return root.nodes[ch].isword
                else:
                    return self.search_helper(word, idx+1, root.nodes[ch])
        
        

# Your WordDictionary object will be instantiated and called as such:
# wordDictionary = WordDictionary()
# wordDictionary.addWord("word")
# wordDictionary.search("pattern")

Idea

Use Trie structure to store words and make search. Assume we have O(N) words and each word has O(K) length. Then each add takes O(K) time and O(K) space. Each search takes O(K) time . See another post: https//nb4799.neu.edu/wordpress/?p=1162

https://leetcode.com/problems/meeting-rooms/

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 canAttendMeetings(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: bool
        """
        if not intervals or len(intervals) == 1:
            return True
        
        intervals = sorted(intervals, key=lambda x: x.start)
        
        for i in xrange(1, len(intervals)):
            if intervals[i].start < intervals[i-1].end:
                return False
        
        return True

Idea

You have to sort first which takes O(nlogn) time.

You can also look at the similar problem: https//nb4799.neu.edu/wordpress/?p=2205 

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

Code

class MovingAverage(object):

    def __init__(self, size):
        """
        Initialize your data structure here.
        :type size: int
        """
        self.size = size
        self.vals = [0]* size
        self.cnt = 0
        self.sum = 0

    def next(self, val):
        """
        :type val: int
        :rtype: float
        """
        self.cnt += 1
        idx = (self.cnt - 1) % self.size 

        # replace old value
        self.sum -= self.vals[idx]
        self.sum += val
        self.vals[idx] = val

        return float(self.sum) / self.cnt if self.cnt < self.size \
            else float(self.sum) / self.size

# Your MovingAverage object will be instantiated and called as such:
# obj = MovingAverage(size)
# param_1 = obj.next(val)

Idea

A cyclic list

You can also use deque however when you calculate average it takes O(K) time where K is the window size.: https://discuss.leetcode.com/topic/44116/4-line-python-solution-using-deque

Code

class Solution(object):
    def findMissingRanges(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: List[str]
        """
        if nums is None:
            nums = []
        
        res = []
        nums = [lower-1] + nums + [upper+1]

        for i in xrange(1, len(nums)):
            prev, cur = nums[i-1], nums[i]
            if cur - prev == 2:
                res.append(str(cur-1))
            elif cur - prev > 2:
                res.append(str(prev+1) + '->' + str(cur-1))

        return res

Idea

To make the code consistent in different cases, I add lower-1 in front of nums and append upper+1 in the end of nums. Then if the current element is exactlye greater than the previous element by 2, then we miss a single number; else, if the current element is greater than the previous element more than 2, then we miss a range; if the current element is just 1 greater than the previous element, we do not do anything.

Also see a similar question: https//nb4799.neu.edu/wordpress/?p=944

dir
    subdir1
    subdir2
        file.ext

dir
    subdir1
        file1.ext
        subsubdir1
    subdir2
        subsubdir2
            file2.ext

Code

class Solution(object):
    def lengthLongestPath(self, input):
        """
        :type input: str
        :rtype: int
        """
        if not input:
            return 0
        
        longest = 0
        prev_tab_cnt = 0
        # store tuples (name, level)
        stk = []

        s = input.split('\n')
        
        for ss in s:
            ss_tab_cnt = 0
            while ss.startswith('\t'):
                ss_tab_cnt += 1
                # \t only takes one character
                ss = ss[1:]
            
            while stk and stk[-1][1] >= ss_tab_cnt:
                stk.pop()
            stk.append((ss, ss_tab_cnt))
            if self.isfile(ss):
                longest = max(longest, len('/'.join(map(lambda x: x[0], stk))))

        return longest

    def isfile(self, s):
        if s.startswith('.') or len(s.split('.')) >= 2:
            return True
        else:
            return False

Idea

Maintain a stack which stores the names of file/directory as well as their levels. Whenever you see it is a file name, concatenate all names in the stack. Whenever you see the current level is less than the stack top’s level, that means the previous trace has ended and the current file/directory starts from some upper level. So you need to pop stack (line 24~25).

You can change stack to dictionary. Reference: https://discuss.leetcode.com/topic/55097/simple-python-solution