0%

# Leetcode

## List

Tricks

1. `Counter()` can be used to create a `defaultdict(int)`

### I do not know….

1. String Compression

1. Repeated String Match

### Pure programming

1. Find and Replace Pattern

1. Minimum Time Difference

1. Valid Palindrome II

1. Reverse String II
1. Group Shifted Strings

1. Substring with Concatenation of All Words

1. Reverse Words in a String III

1. String Compression

1. Multiply Strings
``````1234567891011121314class Solution:      def multiply(self, num1: str, num2: str) -> str:          if num1 == '0' or num2 == '0': return '0'          num1, num2 = num1[::-1], num2[::-1]          m, n = len(num1), len(num2)          rst = [0] * (m+n)          for i1, v1 in enumerate(num1):              for i2, v2 in enumerate(num2):                  rst[i1+i2] += int(v1) * int(v2)                  rst[i1+i2+1] += rst[i1+i2] // 10                  rst[i1+i2] %= 10          while rst[-1] == 0:              rst.pop()          return ''.join(map(str, rst))[::-1]
``````
1. Before and After Puzzle

1. Goat Latin

1. Complex Number Multiplication

https://leetcode.com/problems/complex-number-multiplication/discuss/702715/Python-Concise-%2B-Straightforward

1. Find And Replace in String

1. LRU Cache

1. Reorganize String

1. Brace Expansion II

1. Expressive Words

1. Remove Duplicate Letters

1. Encode and Decode Strings

https://leetcode.com/problems/encode-and-decode-strings/discuss/715649/Python-Straightforward

1. Swap For Longest Repeated Character Substring

1. Minimum Swaps to Make Strings Equal

1. Last Substring in Lexicographical Order
1. Longest Uncommon Subsequence II

1. Stamping The Sequence

1. Reverse Words in a String II

https://leetcode.com/problems/reverse-words-in-a-string-ii/discuss/715615/Python-Concise-In-place

### Palindromic

Manacher’s Algorithm

1. Longest Palindromic Substring

1. Palindromic Substrings

O(N^2) - None Manacher’s Algorithm

1. Palindrome Pairs

### Math

I do not know.
You tell me how to solve it.

1. Orderly Queue

### Sliding window

Maintain a state while sliding window

• easy

1. Dictionary, Dictionary, Dictionary
2. Prefix_sum
1. Longest Substring Without Repeating Characters

1. Find Two Non-overlapping Sub-arrays Each With Target Sum

1. Minimum Window Substring

1. Longest Substring with At Most Two Distinct Characters

1. Number of Substrings Containing All Three Characters

• Monotone Stack

1. Largest Rectangle in Histogram

1. Maximal Rectangle

1. Final Prices With a Special Discount in a Shop
1. Next Greater Element III

1. Maximum Binary Tree

• Monotone queue

• stack

O(1) to push and pop at end.

1. Valid Parentheses

1. Basic Calculator II

1. Minimum Remove to Make Valid Parentheses

### Heap sort / Priority Queue

1. Smallest Range Covering Elements from K Lists

Binary Search

Ideal

• Binary search can be used to guess answer in a known range.

Leverage library if it is available.

• Python: `bisect.bisect_left`, `bisect.bisect_right`
• C++: `lower_bound`, `upper_bound`
1. Design Log Storage System

1. Split Array Largest Sum

Guess answer by using binary search

1. Minimum Number of Days to Make m Bouquets

1. Snapshot Array

### KMP

1. Shortest Palindrome

1. Shortest Palindrome

## Dynamic programming

Idea

1. DP is a smart brute force. It remember state while exhausting all possible cases.
2. DP is a DFS. Switching to BFS when it is too slow or taking too much memory to do DFS.
3. Transformation formula is the key of DP. `Bottom up` or `Top down` is just the implementation technical.
4. `Bottom up` implementation can be used to save memory when we only need states from last n levels.
5. Pay attention to edge cases. Edge cases used to happen when each parameter(dimension variable) reaching 0.
E.g. 10. Regular Expression Matching

1. Climbing Stairs

1. House Robber

1. Triangle
1. Counting Bits

1. Best Time to Buy and Sell Stock with Cooldown

1. Perfect Squares
1. Ugly Number II
1. Count Numbers with Unique Digits

### Three dimension

1. Paint House III

https://leetcode.com/problems/paint-house-iii/discuss/674485/Python-Solution

## Tree

Recursive! Recursive! Recursive!

## Recursive to Non-recursive

### DFS

1. Construct String from Binary Tree

1. Same Tree

1. Symmetric Tree

1. Binary Search Tree Iterator

1. Generate Parentheses

1. Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/719416/Python-Concise-Recursive-%2B-Non-recursive

1. Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/discuss/719653/Python-Concise-Recursive-%2B-Optimized-recursive-%2B-Non-recursive

1. Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/719519/Python-Concise-Recursive-%2B-Non-recursive

1. Remove Invalid Parentheses

DFS is simple. It is only the matter of how many unnecessary subtree we can cut.

### BFS

1. Binary Tree Right Side View

1. Remove Invalid Parentheses
1. Perfect Squares

### Trie

1. Search Suggestions System

### Binary Lifting

1. Kth Ancestor of a Tree Node

### Binary Index Tree

Wikipedia: A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

1. Minimum Possible Integer After at Most K Adjacent Swaps On Digits