演算法與資料結構
  • 簡介
  • 前言
    • 事前準備
    • 資料結構場景
    • 複雜度分析
      • 時間複雜度
      • 空間複雜度
  • 分類題型
    • Array 陣列
      • 88. Merge Sorted Array
      • 1089. Duplicate Zeros
      • 941. Valid Mountain Array
      • 1710. Maximum Units on a Truck
      • 54. Spiral Matrix
      • 73. Set Matrix Zeroes
      • 498. Diagonal Traverse
      • 238. Product of Array Except Self
      • HackerRank Counting Valleys
      • 1089. Duplicate Zeros
    • Backtrack 回溯法
      • 51. & 52. N Queens
      • 37. Sudoku Solver
      • 77. Combinations
      • 39. Combination Sum
        • 40. Combination Sum II
        • 216. Combination Sum III
      • 78. Subsets
        • 90. Subsets II
      • 46. Permutations
        • 47. Permutations II
      • 22. Generate Parentheses
      • 1087. Brace Expansion
      • 332. Reconstruct Itinerary
      • 489. Robot Room Cleaner
      • 17. Letter Combinations of a Phone Number
      • 79. Word Search
        • 212. Word Search II
      • 425. Word Squares
      • 1219. Path with Maximum Gold
      • 247. Strobogrammatic Number II
    • Binary Search 二分搜索
      • Rotated Array 旋轉陣列問題
        • 33. Search in Rotated Sorted Array
        • 81. Search in Rotated Sorted Array II
        • 153. Find Minimum in Rotated Sorted Array
        • 154. Find Minimum in Rotated Sorted Array II
      • 374. Guess Number Higher or Lower
      • 704. Binary Search
      • 34. Find First and Last Position of Element in Sorted Array
      • 69. Sqrt(x)
      • 367. Valid Perfect Square
      • 374. Guess Number Higher or Lower
      • 278. First Bad Version
      • 162. Find Peak Element
      • 852. Peak Index in a Mountain Array
      • 35. Search Insert Position
      • 875. Koko Eating Bananas
      • 1011. Capacity To Ship Packages Within D Days
      • 173. Binary Search Tree Iterator
      • 1586. Binary Search Tree Iterator II
    • Dynamic Programming 動態規劃
      • 509. Fibonacci Number
      • 70. Climbing Stairs
      • 55. Jump Game
      • 62. Unique Paths
      • 64. Minimum Path Sum
      • 174. Dungeon Game
      • 91. Decode Ways
      • 72. Edit Distance
      • 221. Maximal Square
      • 329. Longest Increasing Path in a Matrix
      • 198. House Robber
        • 213. House Robber II
      • 1109. Corporate Flight Bookings
      • 983. Minimum Cost For Tickets
      • 1143. Longest Common Subsequence
        • 583. Delete Operation for Two Strings
        • 712. Minimum ASCII Delete Sum for Two Strings
      • 53. Maximum Subarray
      • 152. Maximum Product Subarray
      • 975. Odd Even Jump
      • 115. Distinct Subsequences
      • 416. Partition Equal Subset Sum
      • 10. Regular Expression Matching
      • 651. 4 Keys Keyboard
    • Hash Table/Set 雜湊表
      • 242. Valid Anagram
      • 49. Group Anagrams
      • 217. Contains Duplicate
        • 219. Contains Duplicate II
        • 220. Contains Duplicate III
      • 187. Repeated DNA Sequences
      • 1170. Compare Strings by Frequency of the Smallest Character
      • 448. Find All Numbers Disappeared in an Array
      • 560. Subarray Sum Equals K
      • 1010. Pairs of Songs With Total Durations Divisible by 60
    • Heap 堆
      • 347. Top K Frequent Elements
      • 692. Top K Frequent Words
      • 973. K Closest Points to Origin
      • 128. Longest Consecutive Sequence
      • 1167. Minimum Cost to Connect Sticks
    • Linked List 鏈結串列
      • 876. Middle of the Linked List
      • 21. Merge Two Sorted Lists
        • 23. Merge k Sorted Lists
      • 148. Sort List
      • 206. Reverse Linked List
        • 92. Reverse Linked List II
    • Stack 棧
      • 20. Valid Parentheses
      • 394. Decode String
      • 84. Largest Rectangle in Histogram
      • 155. Min Stack
    • String 字串
      • 43. Multiply Strings
      • 344. Reverse String
      • 726. Number of Atoms
      • 8. String to Integer (atoi)
      • 12. Integer to Roman
      • 696. Count Binary Substrings
    • Tree 樹
      • Breadth-first search 廣度優先搜索
        • 111. Minimum Depth of Binary Tree
        • 200. Number of Islands
        • 752. Open the Lock
        • 279. Perfect Squares
        • 286. Walls and Gates
        • 417. Pacific Atlantic Water Flow
        • 994. Rotting Oranges
        • 429. N-ary Tree Level Order Traversal
        • 116. Populating Next Right Pointers in Each Node
        • 117. Populating Next Right Pointers in Each Node II
        • 430. Flatten a Multilevel Doubly Linked List
        • 1135. Connecting Cities With Minimum Cost
      • Preorder 前序遍歷
        • 105. Construct Binary Tree from Preorder and Inorder Traversal
        • 144. Binary Tree Preorder Traversal
        • 589. N-ary Tree Preorder Traversal
        • 255. Verify Preorder Sequence in Binary Search Tree
      • Inorder 中序遍歷
        • 94. Binary Tree Inorder Traversal
        • 426. Convert Binary Search Tree to Sorted Doubly Linked List
      • Postorder 後序遍歷
        • 106. Construct Binary Tree from Inorder and Postorder Traversal
        • 145. Binary Tree Postorder Traversal
        • 590. N-ary Tree Postorder Traversal
        • 114. Flatten Binary Tree to Linked List
        • 652. Find Duplicate Subtrees
        • 124. Binary Tree Maximum Path Sum
        • 543. Diameter of Binary Tree
        • 337. House Robber III
      • BST
        • 98. Validate Binary Search Tree
        • 450. Delete Node in a BST
        • 700. Search in a Binary Search Tree
        • 701. Insert into a Binary Search Tree
        • 1373. Maximum Sum BST in Binary Tree
        • 230. Kth Smallest Element in a BST
        • 99. Recover Binary Search Tree
      • Serialization & Deserialization
        • 606. Construct String from Binary Tree
        • 536. Construct Binary Tree from String
        • 297. Serialize and Deserialize Binary Tree
        • 428. Serialize and Deserialize N-ary Tree
      • Graph 圖
        • 1971. Find if Path Exists in Graph
        • 323. Number of Connected Components in an Undirected Graph
        • 547. Number of Provinces
      • 100. Same Tree
        • 572. Subtree of Another Tree
      • 1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree
      • 226. Invert Binary Tree
      • 104. Maximum Depth of Binary Tree
      • 559. Maximum Depth of N-ary Tree
      • 102. Binary Tree Level Order Traversal
      • 261. Graph Valid Tree
      • 250. Count Univalue Subtrees
      • 222. Count Complete Tree Nodes
      • 112. Path Sum
      • 113. Path Sum II
      • 437. Path Sum III
    • Trie 字典樹
      • 208. Implement Trie (Prefix Tree)
      • 677. Map Sum Pairs
      • 648. Replace Words
      • 588. Design In-Memory File System
      • 642. Design Search Autocomplete System
      • 211. Design Add and Search Words Data Structure
      • 1268. Search Suggestions System
    • Two Pointers 雙指針
      • 977. Squares of a Sorted Array
      • 1095. Find in Mountain Array
      • 27. Remove Element
      • 141. Linked List Cycle
        • 142. Linked List Cycle II
      • 19. Remove Nth Node From End of List
      • 26. Remove Duplicates from Sorted Array
      • 83. Remove Duplicates from Sorted List
      • 283. Move Zeroes
    • Sliding Window 滑動窗口
      • 3. Longest Substring Without Repeating Characters
      • 76. Minimum Window Substring
      • 567. Permutation in String
      • 438. Find All Anagrams in a String
      • 424. Longest Repeating Character Replacement
      • 485. Max Consecutive Ones
      • 1004. Max Consecutive Ones III
      • 904. Fruit Into Baskets
      • 1248. Count Number of Nice Subarrays
      • 1358. Number of Substrings Containing All Three Characters
      • 1234. Replace the Substring for Balanced String
      • 930. Binary Subarrays With Sum
      • 209. Minimum Size Subarray Sum
      • 992. Subarrays with K Different Integers
      • 713. Subarray Product Less Than K
      • 862. Shortest Subarray with Sum at Least K
      • 239. Sliding Window Maximum
      • 159. Longest Substring with At Most Two Distinct Characters
      • 340. Longest Substring with At Most K Distinct Character
      • 992. Subarrays with K Different Integers
    • Bit Manipulation 位元運算
      • 136. Single Number
      • 7. Reverse Integer
      • 191. Number of 1 Bits
    • Math 數學
      • 553. Optimal Division
      • 204. Count Primes
      • 372. Super Pow
      • 829. Consecutive Numbers Sum
      • 1492. The kth Factor of n
    • Other 其他
      • 31. Next Permutation
      • 1446. Consecutive Characters
      • 386. Lexicographical Numbers
      • 269. Alien Dictionary
      • 48. Rotate Image
      • 157. Read N Characters Given Read4
        • 158. Read N Characters Given Read4 II - Call multiple times
      • 246. Strobogrammatic Number
    • Object Oriented Design 物件導向設計
      • 710. Random Pick with Blacklist
      • 380. Insert Delete GetRandom O(1)
      • 271. Encode and Decode Strings
      • 348. Design Tic-Tac-Toe
  • 經典題目
    • Best Time to Buy and Sell Stock 股票買賣問題
      • 121. Best Time to Buy and Sell Stock
      • 122. Best Time to Buy and Sell Stock II
      • 123. Best Time to Buy and Sell Stock III
      • 188. Best Time to Buy and Sell Stock IV
      • 309. Best Time to Buy and Sell Stock with Cool down
      • 714. Best Time to Buy and Sell Stock with Transaction Fee
    • Palindrome 回文
      • 125. Valid Palindrome
      • 680. Valid Palindrome II
      • 266. Palindrome Permutation
      • 9. Palindrome Number
      • 866. Prime Palindrome
      • 5. Longest Palindromic Substring
      • 647. Palindromic Substrings
      • 516. Longest Palindromic Subsequence
      • 1930. Unique Length-3 Palindromic Subsequences
      • 234. Palindrome Linked List
    • Time Intervals 時間區間問題
      • 252. Meeting Rooms
      • 253. Meeting Rooms II
      • 56. Merge Intervals
      • 57. Insert Interval
      • 495. Teemo Attacking
      • 759. Employee Free Time
      • 986. Interval List Intersections
      • 435. Non-overlapping Intervals
      • 452. Minimum Number of Arrows to Burst Balloons
      • 729. My Calendar I
      • 731. My Calendar II
      • 732. My Calendar III
      • 163. Missing Ranges
      • 1024. Video Stitching
    • Calculator 計算機問題
      • 224. Basic Calculator
      • 227. Basic Calculator II
      • 772. Basic Calculator III
    • Add One 加一問題
      • 66. Plus One
      • 67. Add Binary
      • 369. Plus One Linked List
      • 2. Add Two Numbers
        • 445. Add Two Numbers II
      • 989. Add to Array-Form of Integer
    • Clone Graph 複製圖形
      • 133. Clone Graph
      • 1490. Clone N-ary Tree
      • 138. Copy List with Random Pointer
      • 1485. Clone Binary Tree With Random Pointer
    • Cache 快取問題
      • 146. LRU Cache 最久未使用演算法
      • 460. LFU Cache 最近最少使用演算法
    • n Sum 問題
      • 1. 2 Sum
      • 15. 3Sum
      • 18. 4Sum
      • 454. 4 Sum II
      • 167. Two Sum II - Input array is sorted
      • 170. Two Sum III - Data structure design
      • 653. Two Sum IV - Input is a BST
      • 16. 3Sum Closest
      • 259. 3Sum Smaller
      • 16. 3Sum Closest
    • Lowest Common Ancestor of a Binary Tree 最近共同祖先問題
    • The Maze 球滾迷宮問題
      • 490. The Maze
      • 505. The Maze II
    • Find Median 尋找中位數
      • 295. Find Median from Data Stream
      • 4. Median of Two Sorted Arrays
    • Course 課程問題
      • 207. 210. Course Schedule I & II
      • 1136. Parallel Courses
    • Coin Change 零錢問題
      • 322. Coin Change
      • 518. Coin Change 2
    • Binary Indexed Tree 樹狀陣列或二元索引樹
      • 303. Range Sum Query - Immutable
      • 307. Range Sum Query - Mutable
      • 315. Count of Smaller Numbers After Self
    • Longest Increasing Subsequence 最長遞增子序列的問題
      • 300. Longest Increasing Subsequence
      • 354. Russian Doll Envelopes
      • 673. Number of Longest Increasing Subsequence
    • Robot Bounded In Circle 掃地機器人
    • Containing Water 裝水問題
      • 11. Container With Most Water
      • 42. Trapping Rain Water
      • 755. Pour Water
    • Word Ladder 文字梯問題
      • 127. Word Ladder
      • 126. Word Ladder II
    • Egg Drop 高樓扔雞蛋
    • Custom sorting 排序技巧
      • 937. Reorder Data in Log Files
    • Word Break 字串組合問題
      • 139. Word Break
      • 140. Word Break II
      • 472. Concatenated Words
  • 常見演算法
    • Sorting 排序
      • Merge Sort (Accepted)
      • Quick Sort (Accepted)
      • Heap Sort (Accepted)
      • Bubble Sort (TLE)
      • Insertion Sort (TLE)
      • Selection Sort (TLE)
    • Shuffle Array 打亂陣列內的元素
    • 池塘抽樣
      • 382. Linked List Random Node
      • 398. Random Pick Index
  • Python 技巧
    • 陣列複製
    • 矩陣操作
      • 向矩陣中的四個方向移動
      • 矩陣遍歷的方法
Powered by GitBook
On this page

Last updated 2 years ago

Trie 是利用 Hash Table 的優勢所衍伸出的一種資料格式，很常被應用在的題目，因為，而且題目通常不會給出任何可以使用出 Trie 的提示，所以通常都會需要自己去建立 TrieNode 這個物件，並且題目很常會需要在 Trie 的節點上去記錄一些資訊。

這些資訊很重要是因為，Trie 的遍歷是一般而言依靠著 DFS 在執行的，這些記錄在 TrieNode 上的資訊有助於我們快速查找到答案，或是減少搜索的空間。

最簡單可以上手的題目是從 開始

物件導向程式設計
208. Implement Trie (Prefix Tree)
Previous437. Path Sum IIINext208. Implement Trie (Prefix Tree)
  1. 分類題型

Trie 字典樹