西雅图打卡

85. Maximal RectangleProblem: Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Solution: DP
思路是参照大神：https://leetcode.com/problems/ma ... hare-my-DP-solution


76. Minimum Window Substring
Problem: Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
Solution: 经典Sliding window

794. Valid Tic-Tac-Toe StateProblem: Return True if and only if it is possible to reach this board position during the course of a valid tic-tac-toe game.
Solution: Ensure 2 things: 1. Number of 'x' equal to number of 'o' or bigger than 1.
                                     2. 1) if 'o' wins, # of 'x' = # of 'o'
                                         2) if 'x' wins, 1 or 2 line(s) with same symbol
                                         3) if no one wins, 0 line with same symbbol

301. Remove Invalid Parentheses
Problem: Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.
Solution: Count the number of left and right parentheses that should be removed at first. Use DFS to find out all solutions.

211. Add and Search Word - Data structure design
Problem: Design a data structure that supports the following two operations: void addWord(word) & bool search(word)
Solution: Construct the Trie data structure. If find '.', use dfs to recur every character.

791. Custom Sort StringProblem: Given S in a custom order, return any permutation of T (as a string) that satisfies the order in S.
Solution: Count the number of each character in T. First, add characters in S (which has order) to the result. Last, add characters without order.

23. Merge k Sorted Lists
Problem: Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution: Priority queue O(NlogN)

124. Binary Tree Maximum Path Sum
Problem: Given a non-empty binary tree, find the maximum path sum.
Solution: Recursion. Compare substree (left, right) and root value, 2 situations.

71. Simplify PathProblem: Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.
Solution: Stack

224. Basic CalculatorProblem: Implement a basic calculator to evaluate a simple expression string.
Solution: Stack

843. Guess the Word
Problem: Guess the word at most 10 times.
Solution: Minimax. 算法效率优化

809. Expressive Words
Problem: Given a list of query words, return the number of words that are stretchy.
Solution: two pointers