76. Minimum Window Substring
Description: Solution: countT, window will be what we "have" & what we "need" We update our window[c]. Does window[c] satisfiy 'window[c] == countT'? Time Complexity: O(n)
Description: Solution: countT, window will be what we "have" & what we "need" We update our window[c]. Does window[c] satisfiy 'window[c] == countT'? Time Complexity: O(n)
Description: Solution: count will store the number of letters of each chracters. res is the longest length of substring we can have. There will be two pointers: r, l Moving r pointer, we count the character. If the length(substring) - (count of bigger character) is bigger than k, we should move l pointer. Then, update the max res. Time Complexity: O(n)
Description: Solution: We use set() for substring. (Sliding Window) In example 1, the string is abcabcbb. We are gonna store substring until meet duplicated character. abc -> now we meet "a" Remove the first "a", now new substring is bca. The length of substring should be r - l + 1. Time Complexity: O(n) Space Complexity: O(n)
Description: Solution: For solving this problem, we use TrieNode (prefix tree). In serach(), we use recursion method to check "." if c is "." we are gonna check the values next to the "." We put the values in dfs() from the next one, so that check recursively by increasing i.
Description: Solution: We make a TrieNode() class. In TrieNode(), we have two attribute: children, endOfWord In insert(), if c is not in cur.children, we put the c in it. And mark the last character as endOfWord. In search(), if c is not in cur.children, we return False. In startsWith(), it is same with search function. But, we use prefix in this case.
Description: Solution: Start from root. If both p, q is less than root, we are gonna see the left portion of root. elif both p, q is more than root, we are gonna see the right portion of root. Other cases have a root as a LCA node in the Tree. Time Complextiy: O(logn) Space Complexity: O(1)
Description: Solution: First, we keep going left in tree. We put the values in stack. Pop the value from the stack. => From most smallest value. Everytime we pop, increase n to check if there is kth smallest value. If it doensn't exist, now we can go right at current node to see the next.
Description: Solution: serialize() if node is None --> append('n') if node exist --> append(str(node.val)) We should search from left! ','.join(res) => ['a', 'b', 'c'] --> "a,b,c" deserialize() data.split(",") => "a,b,c" --> ['a', 'b', 'c'] self.i is the global variable 'n' means null, so return null. Don't forgetself.i += 1 We are gonna append TreeNode object. '(val)' is the string form, so we ..
Description: Solution: In helper(), we are gonna update the boundary to check the val is satisfied in boundary condition. min_val is the left boundary. max_val is the right boundary. helper() return the new boundary. "-2**31-1" and "2**31" are the initial value for the root value. It represents "-∞