📖
LeetCode
  • Introduction
  • Array
    • 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
    • 1.Two-Sum
    • 1007.Minimum-Domino-Rotations-For-Equal-Row
    • 1031.Maximum-Sum-of-Two-Non-Overlapping-Subarrays
    • 1052.Grumpy-Bookstore-Owner
    • 11.Container-With-Most-Water
    • 1122.Relative-Sort-Array
    • 1163.Last-Substring-in-Lexicographical-Order
    • [118.Pascal's-Triangle](Array/118.Pascal's-Triangle.md)
    • 1181.Before-and-After-Puzzle
    • 1231.Divide-Chocolate
    • 1296.Divide-Array-in-Sets-of-K-Consecutive-Numbers
    • 1304.Find-N-Unique-Integers-Sum-up-to-Zero
    • 134.Gas-Station
    • 135.Candy
    • 1352.Product-of-the-Last-K-Numbers
    • 136.Single-Number
    • 14.Longest-Common-Prefix
    • 1477.Find-Two-Non-overlapping-Sub-arrays-Each-With-Target-Sum
    • 15.3Sum
    • 152.Maximum-Product-Subarray
    • 16.3Sum-Closest
    • 163.Missing-Ranges
    • 169.Majority-Element
    • 18.4Sum
    • 189.Rotate-Array
    • 204.Count-Primes
    • 215.Kth-Largest-Element-in-an-Array
    • 217.Contains-Duplicate
    • 219.Contains-Duplicate-II
    • 220.Contains-Duplicate-III
    • 228.Summary-Ranges
    • 229.Majority-Element-II
    • 238.Product-of-Array-Except-Self
    • 239.Sliding-Window-Maximum
    • 243.Shortest-Word-Distance
    • 252.Meeting-Rooms
    • 266.Palindrome-Permutation
    • 268.Missing-Number
    • 273.Integer-to-English-Words
    • 279.Perfect-Squares
    • 283.Move-Zeroes
    • 287.Find-the-Duplicate-Number
    • 29.Divide-Two-Integers
    • 299.Bulls-and-Cows
    • 31.Next-Permutation
    • 325.Maximum-Size-Subarray-Sum-Equals-k
    • 334.Increasing-Triplet-Subsequence
    • 340.Longest-Substring-with-At-Most-K-Distinct-Characters
    • 347.Top-K-Frequent-Elements
    • 349.Intersection-of-Two-Arrays
    • 350.Intersection-of-Two-Arrays-II
    • 354.Russian-Doll-Envelopes
    • 367.Valid-Perfect-Square
    • 378.Kth-Smallest-Element-in-a-Sorted-Matrix
    • 38.Count-and-Say
    • 383.Ransom-Note
    • 387.First-Unique-Character-in-a-String
    • 4.Median-of-Two-Sorted-Arrays
    • 406.Queue-Reconstruction-by-Height
    • 410.Split-Array-Largest-Sum
    • 412.Fizz-Buzz
    • 419.Battleships-in-a-Board
    • 435.Non-overlapping-Intervals
    • 438.Find-All-Anagrams-in-a-String
    • 442.Find-All-Duplicates-in-an-Array
    • 457.Circular-Array-Loop
    • 509.Fibonacci-Number
    • 53.Maximum-Subarray
    • 539.Minimum-Time-Difference
    • 540.Single-Element-in-a-Sorted-Array
    • 56.Merge-Intervals
    • 560.Subarray-Sum-Equals-K
    • 57.Insert-Interval
    • 575.Distribute-Candies
    • 581.Shortest-Unsorted-Continuous-Subarray
    • 593.Valid-Square
    • 6.ZigZag-Conversion
    • 609.Find-Duplicate-File-in-System
    • 611.Valid-Triangle-Number
    • 621.Task-Scheduler
    • 628.Maximum-Product-of-Three-Numbers
    • 632.Smallest-Range-Covering-Elements-from-K-Lists
    • 659.Split-Array-into-Consecutive-Subsequences
    • 67.Add-Binary
    • 670.Maximum-Swap
    • 7.Reverse-Integer
    • 717.1-bit-and-2-bit-Characters
    • 722.Remove-Comments
    • 724.Find-Pivot-Index
    • 763.Partition-Labels
    • 811.Subdomain-Visit-Count
    • 845.Longest-Mountain-in-Array
    • 846.Hand-of-Straights
    • 862.Shortest-Subarray-with-Sum-at-Least-K
    • 866.Prime-Palindrome
    • 881.Boats-to-Save-People
    • 937.Reorder-Data-in-Log-Files
    • 953.Verifying-an-Alien-Dictionary
    • 957.Prison-Cells-After-N-Days
    • 973.K-Closest-Points-to-Origin
    • 974.Subarray-Sums-Divisible-by-K
    • 995.Minimum-Number-of-K-Consecutive-Bit-Flips
    • Interleaving Positive And Negative Numbers
    • Maximum Subarray Difference
    • Maximum Subarray Ii
    • Merge Sorted Array Ii
    • Minimum Subarray
    • Partition Array
    • Recover Rotated Sorted Array
    • Subarray Sum Closest
    • Subarray Sum Zero
  • Basic Knowledge
    • Binary Tree
    • Bit Operation
    • Heapify
    • Java Syntax
    • Monotonous Stack
    • Trie Tree
  • Binary Search
    • 1011.Capacity-To-Ship-Packages-Within-D-Days
    • 1044.Longest-Duplicate-Substring
    • 1062.Longest-Repeating-Substring
    • 153.Find-Minimum-in-Rotated-Sorted-Array
    • 162.Find-Peak-Element
    • 278.First-Bad-Version
    • 33.Search-in-Rotated-Sorted-Array
    • 34.Find-First-and-Last-Position-of-Element-in-Sorted-Array
    • 35.Search-Insert-Position
    • [50.Pow(x,-n)](Binary-Search/50.Pow(x,-n).md)
    • [69.Sqrt(x)](Binary-Search/69.Sqrt(x).md)
    • 704.Binary-Search
    • 74.Search-a-2D-Matrix
    • 785.Is-Graph-Bipartite?
    • 796.Rotate-String
    • 81.Search-in-Rotated-Sorted-Array-II
    • Count Of Smaller Number
    • Median
    • Search In A Big Sorted Array
  • Binary Tree
    • Serialize And Deserialize
      • 297.Serialize-and-Deserialize-Binary-Tree
      • 428.Serialize-and-Deserialize-N-ary-Tree
      • 449.Serialize-and-Deserialize-BST
    • 100.Same-Tree
    • 101.Symmetric-Tree
    • 1038.Binary-Search-Tree-to-Greater-Sum-Tree
    • 105.Construct-Binary-Tree-from-Preorder-and-Inorder-Traversal
    • 106.Construct-Binary-Tree-from-Inorder-and-Postorder-Traversal
    • 108.Convert-Sorted-Array-to-Binary-Search-Tree
    • 1110.Delete-Nodes-And-Return-Forest
    • 114.Flatten-Binary-Tree-to-Linked-List
    • 1145.Binary-Tree-Coloring-Game
    • 116.Populating-Next-Right-Pointers-in-Each-Node
    • 117.Populating-Next-Right-Pointers-in-Each-Node-II
    • 129.Sum-Root-to-Leaf-Numbers
    • 144.Binary-Tree-Preorder-Traversal
    • 199.Binary-Tree-Right-Side-View
    • 222.Count-Complete-Tree-Nodes
    • 226.Invert-Binary-Tree
    • 230.Kth-Smallest-Element-in-a-BST
    • 257.Binary-Tree-Paths
    • 270.Closest-Binary-Search-Tree-Value
    • 285.Inorder-Successor-in-BST
    • 337.House-Robber-III
    • 426.Convert-Binary-Search-Tree-to-Sorted-Doubly-Linked-List
    • 510.Inorder-Successor-in-BST-II
    • 543.Diameter-of-Binary-Tree
    • 617.Merge-Two-Binary-Trees
    • 652.Find-Duplicate-Subtrees
    • 653.Two-Sum-IV---Input-is-a-BST
    • 662.Maximum-Width-of-Binary-Tree
    • 669.Trim-a-Binary-Search-Tree
    • 889.Construct-Binary-Tree-from-Preorder-and-Postorder-Traversal
    • 938.Range-Sum-of-BST
    • 94.Binary-Tree-Inorder-Traversal
    • 951.Flip-Equivalent-Binary-Trees
    • 958.Check-Completeness-of-a-Binary-Tree
    • 979.Distribute-Coins-in-Binary-Tree
    • 987.Vertical-Order-Traversal-of-a-Binary-Tree
    • Search Range In Binary Search Tree
  • Bit
    • 307.Range-Sum-Query---Mutable
    • 308.Range-Sum-Query-2D---Mutable
    • 315.Count-of-Smaller-Numbers-After-Self
    • 493.Reverse-Pairs
  • Data Structure
    • Basic Calculator
      • 224.Basic-Calculator
      • 227.Basic-Calculator-II
      • 772.Basic-Calculator-III
      • Basic Claculator Iv
    • 1146.Snapshot-Array
    • 1152.Analyze-User-Website-Visit-Pattern
    • 1167.Minimum-Cost-to-Connect-Sticks
    • 1172.Dinner-Plate-Stacks
    • 1236.Web-Crawler
    • 128.Longest-Consecutive-Sequence
    • 146.LRU-Cache
    • 155.Min-Stack
    • 158.Read-N-Characters-Given-Read4-II---Call-multiple-times
    • 225.Implement-Stack-using-Queues
    • 232.Implement-Queue-using-Stacks
    • 253.Meeting-Rooms-II
    • 263.Ugly-Number
    • 271.Encode-and-Decode-Strings
    • [28.Implement-strStr()](Data-Structure/28.Implement-strStr().md)
    • 281.Zigzag-Iterator
    • 284.Peeking-Iterator
    • 295.Find-Median-from-Data-Stream
    • 314.Binary-Tree-Vertical-Order-Traversal
    • 332.Reconstruct-Itinerary
    • 341.Flatten-Nested-List-Iterator
    • 346.Moving-Average-from-Data-Stream
    • 348.Design-Tic-Tac-Toe
    • 353.Design-Snake-Game
    • 359.Logger-Rate-Limiter
    • 362.Design-Hit-Counter
    • [380.Insert-Delete-GetRandom-O(1)](Data-Structure/380.Insert-Delete-GetRandom-O(1).md)
    • [381.Insert-Delete-GetRandom-O(1)---Duplicates-allowed](Data-Structure/381.Insert-Delete-GetRandom-O
    • 384.Shuffle-an-Array
    • 41.First-Missing-Positive
    • 460.LFU-Cache
    • [470.Implement-Rand10()-Using-Rand7()](Data-Structure/470.Implement-Rand10()-Using-Rand7().md)
    • 49.Group-Anagrams
    • 523.Continuous-Subarray-Sum
    • 528.Random-Pick-with-Weight
    • 535.Encode-and-Decode-TinyURL
    • 545.Boundary-of-Binary-Tree
    • 572.Subtree-of-Another-Tree
    • 588.Design-In-Memory-File-System
    • 622.Design-Circular-Queue
    • 642.Design-Search-Autocomplete-System
    • 692.Top-K-Frequent-Words
    • 706.Design-HashMap
    • 707.Design-Linked-List
    • 729.My-Calendar-I
    • 731.My-Calendar-II
    • 759.Employee-Free-Time
    • 794.Valid-Tic-Tac-Toe-State
    • 84.Largest-Rectangle-in-Histogram
    • 843.Guess-the-Word
    • 900.RLE-Iterator
    • 937.Reorder-Data-in-Log-Files
    • 981.Time-Based-Key-Value-Store
    • 99.Recover-Binary-Search-Tree
    • Add And Search Word Data Structure Design
    • Heapify
    • Max Tree
    • Rehashing
    • Subarray Sum Zero
  • Divide Conquer
    • 102.Binary-Tree-Level-Order-Traversal
    • 103.Binary-Tree-Zigzag-Level-Order-Traversal
    • 104.Maximum-Depth-of-Binary-Tree
    • 107.Binary-Tree-Level-Order-Traversal-II
    • 110.Balanced-Binary-Tree
    • 124.Binary-Tree-Maximum-Path-Sum
    • 173.Binary-Search-Tree-Iterator
    • 218.The-Skyline-Problem
    • 236.Lowest-Common-Ancestor-of-a-Binary-Tree
    • 450.Delete-Node-in-a-BST
    • 973.K-Closest-Points-to-Origin
    • 98.Validate-Binary-Search-Tree
    • Inorder
    • Insert Node In A Binary Search Tree
    • Postorder
    • Preorder
  • Dynamic Programming
    • 1.position
      • 1048.Longest-String-Chain
      • 198.House-Robber
      • 256.Paint-House
      • 265.Paint-House-II
      • 32.Longest-Valid-Parentheses
      • 338.Counting-Bits
      • 361.Bomb-Enemy
      • 403.Frog-Jump
      • 45.Jump-Game-II
      • 518.Coin-Change-2
      • 55.Jump-Game
      • 62.Unique-Paths
      • 63.Unique-Paths-II
      • 64.Minimum-Path-Sum
      • 70.Climbing-Stairs
      • 72.Edit-Distance
      • 85.Maximal-Rectangle
      • 871.Minimum-Number-of-Refueling-Stops
      • 91.Decode-Ways
      • 97.Interleaving-String
      • 980.Unique-Paths-III
    • 2.sequence
      • Sell Stock
        • 188.Best-Time-to-Buy-and-Sell-Stock-IV
        • 309.Best-Time-to-Buy-and-Sell-Stock-with-Cooldown
      • 115.Distinct-Subsequences
      • 132.Palindrome-Partitioning-II
      • 300.Longest-Increasing-Subsequence
      • 472.Concatenated-Words
      • 516.Longest-Palindromic-Subsequence
      • 727.Minimum-Window-Subsequence
      • 801.Minimum-Swaps-To-Make-Sequences-Increasing
      • K Sum
      • Long Common Sequence
      • Maximum Subarray Iii
      • Minimum Adjustment Cost
    • Backpack Problem
      • 1155.Number-of-Dice-Rolls-With-Target-Sum
      • 322.Coin-Change
      • 416.Partition-Equal-Subset-Sum
      • Backpack Ii
      • Backpack Iii
      • Backpack
    • 区间型
      • 1000.Minimum-Cost-to-Merge-Stones
      • 1335.Minimum-Difficulty-of-a-Job-Schedule
      • 375.Guess-Number-Higher-or-Lower-II
      • 87.Scramble-String
      • Coins In A Line Iii
    • 矩阵坐标
      • 1277.Count-Square-Submatrices-with-All-Ones
      • 221.Maximal-Square
      • 741.Cherry-Pickup
    • 1049.Last-Stone-Weight-II
    • 1140.Stone-Game-II
    • 1235.Maximum-Profit-in-Job-Scheduling
    • 1320.Minimum-Distance-to-Type-a-Word-Using-Two-Fingers
    • 1406.Stone-Game-III
    • 774.Minimize-Max-Distance-to-Gas-Station
    • Longest Arithmetic Sequence
  • Graph Search
    • Word Ladder
      • 126.Word-Ladder-II
      • 127.Word-Ladder
    • 10.Regular-Expression-Matching
    • 1041.Robot-Bounded-In-Circle
    • 1066.Campus-Bikes-II
    • 1087.Brace-Expansion
    • 1102.Path-With-Maximum-Minimum-Value
    • 113.Path-Sum-II
    • 1192.Critical-Connections-in-a-Network
    • 1197.Minimum-Knight-Moves
    • 1219.Path-with-Maximum-Gold
    • 1239.Maximum-Length-of-a-Concatenated-String-with-Unique-Characters
    • 1284.Minimum-Number-of-Flips-to-Convert-Binary-Matrix-to-Zero-Matrix
    • 1293.Shortest-Path-in-a-Grid-with-Obstacles-Elimination
    • 131.Palindrome-Partitioning
    • 133.Clone-Graph
    • 1345.Jump-Game-IV
    • 1376.Time-Needed-to-Inform-All-Employees
    • 139.Word-Break
    • 140.Word-Break-II
    • 1416.Restore-The-Array
    • 17.Letter-Combinations-of-a-Phone-Number
    • 179.Largest-Number
    • 200.Number-of-Islands
    • 212.Word-Search-II
    • 22.Generate-Parentheses
    • 248.Strobogrammatic-Number-III
    • 286.Walls-and-Gates
    • 289.Game-of-Life
    • 298.Binary-Tree-Longest-Consecutive-Sequence
    • 301.Remove-Invalid-Parentheses
    • 312.Burst-Balloons
    • 317.Shortest-Distance-from-All-Buildings
    • 320.Generalized-Abbreviation
    • 323.Number-of-Connected-Components-in-an-Undirected-Graph
    • 329.Longest-Increasing-Path-in-a-Matrix
    • 364.Nested-List-Weight-Sum-II
    • 386.Lexicographical-Numbers
    • 39.Combination-Sum
    • 399.Evaluate-Division
    • 40.Combination-Sum-II
    • 417.Pacific-Atlantic-Water-Flow
    • 430.Flatten-a-Multilevel-Doubly-Linked-List
    • 437.Path-Sum-III
    • 44.Wildcard-Matching
    • 463.Island-Perimeter
    • 465.Optimal-Account-Balancing
    • 489.Robot-Room-Cleaner
    • 490.The-Maze
    • 494.Target-Sum
    • 51.N-Queens
    • 515.Find-Largest-Value-in-Each-Tree-Row
    • 524.Longest-Word-in-Dictionary-through-Deleting
    • 529.Minesweeper
    • 547.Number-of-Provinces
    • 568.Maximum-Vacation-Days
    • 675.Cut-Off-Trees-for-Golf-Event
    • 679.24-Game
    • 695.Max-Area-of-Island
    • 698.Partition-to-K-Equal-Sum-Subsets
    • 721.Accounts-Merge
    • 733.Flood-Fill
    • 737.Sentence-Similarity-II
    • 743.Network-Delay-Time
    • 752.Open-the-Lock
    • 753.Cracking-the-Safe
    • 773.Sliding-Puzzle
    • 79.Word-Search
    • 802.Find-Eventual-Safe-States
    • 815.Bus-Routes
    • 818.Race-Car
    • 854.K-Similar-Strings
    • 863.All-Nodes-Distance-K-in-Binary-Tree
    • 864.Shortest-Path-to-Get-All-Keys
    • 909.Snakes-and-Ladders
    • 93.Restore-IP-Addresses
    • 95.Unique-Binary-Search-Trees-II
    • 96.Unique-Binary-Search-Trees
    • 994.Rotting-Oranges
  • Linked List
    • Add Two Numbers
      • 2.Add-Two-Numbers
      • 445.Add-Two-Numbers-II
    • 109.Convert-Sorted-List-to-Binary-Search-Tree
    • 138.Copy-List-with-Random-Pointer
    • 141.Linked-List-Cycle
    • 142.Linked-List-Cycle-II
    • 143.Reorder-List
    • 148.Sort-List
    • 160.Intersection-of-Two-Linked-Lists
    • 19.Remove-Nth-Node-From-End-of-List
    • 206.Reverse-Linked-List
    • 21.Merge-Two-Sorted-Lists
    • 23.Merge-k-Sorted-Lists
    • 234.Palindrome-Linked-List
    • 237.Delete-Node-in-a-Linked-List
    • 24.Swap-Nodes-in-Pairs
    • 25.Reverse-Nodes-in-k-Group
    • 328.Odd-Even-Linked-List
    • 369.Plus-One-Linked-List
    • 61.Rotate-List
    • 82.Remove-Duplicates-from-Sorted-List-II
    • 83.Remove-Duplicates-from-Sorted-List
    • 86.Partition-List
    • 876.Middle-of-the-Linked-List
    • 92.Reverse-Linked-List-II
    • Remove Duplicates From Unsorted List Geeksforgeeks
  • Matrix
    • Spiral Matrix
      • 54.Spiral-Matrix
      • 59.Spiral-Matrix-II
    • 1074.Number-of-Submatrices-That-Sum-to-Target
    • 1292.Maximum-Side-Length-of-a-Square-with-Sum-Less-than-or-Equal-to-Threshold
    • 240.Search-a-2D-Matrix-II
    • 296.Best-Meeting-Point
    • 304.Range-Sum-Query-2D---Immutable
    • 311.Sparse-Matrix-Multiplication
    • 36.Valid-Sudoku
    • 363.Max-Sum-of-Rectangle-No-Larger-Than-K
    • 37.Sudoku-Solver
    • 48.Rotate-Image
    • 498.Diagonal-Traverse
    • 562.Longest-Line-of-Consecutive-One-in-Matrix
    • 723.Candy-Crush
    • 73.Set-Matrix-Zeroes
    • 835.Image-Overlap
    • 939.Minimum-Area-Rectangle
    • 963.Minimum-Area-Rectangle-II
    • 986.Interval-List-Intersections
    • Friend Circles
  • Mergesort
    • Algorithm Swap
  • Numbers
    • 1088.Confusing-Number-II
    • 13.Roman-to-Integer
    • 166.Fraction-to-Recurring-Decimal
    • 202.Happy-Number
    • 65.Valid-Number
    • 681.Next-Closest-Time
    • 780.Reaching-Points
    • 829.Consecutive-Numbers-Sum
    • 914.X-of-a-Kind-in-a-Deck-of-Cards
    • 991.Broken-Calculator
  • Other
    • 1185.Day-of-the-Week
    • 149.Max-Points-on-a-Line
    • 176.Second-Highest-Salary
    • 20.Valid-Parentheses
    • 277.Find-the-Celebrity
    • 612.Shortest-Distance-in-a-Plane
    • [8.String-to-Integer-(atoi)](Other/8.String-to-Integer-(atoi).md)
  • Permutation And Combination
    • 46.Permutations
    • 47.Permutations-II
    • 60.Permutation-Sequence
    • 77.Combinations
    • 78.Subsets
    • 90.Subsets-II
  • Queue
    • 480.Sliding-Window-Median
    • 853.Car-Fleet
    • 862.Shortest-Subarray-with-Sum-at-Least-K
    • 950.Reveal-Cards-In-Increasing-Order
  • Sort Algorithm
    • 1057.Campus-Bikes
    • 969.Pancake-Sorting
    • Bubble Sort
    • Merge Sort
    • Quick Sort
  • Stack
    • 1130.Minimum-Cost-Tree-From-Leaf-Values
    • 1249.Minimum-Remove-to-Make-Valid-Parentheses
    • 379.Design-Phone-Directory
    • 394.Decode-String
    • 402.Remove-K-Digits
    • 456.132-Pattern
    • 496.Next-Greater-Element-I
    • 503.Next-Greater-Element-II
    • 636.Exclusive-Time-of-Functions
    • 71.Simplify-Path
    • 739.Daily-Temperatures
    • 844.Backspace-String-Compare
    • 917.Reverse-Only-Letters
    • 946.Validate-Stack-Sequences
  • String
    • 1055.Shortest-Way-to-Form-String
    • 1096.Brace-Expansion-II
    • 1100.Find-K-Length-Substrings-With-No-Repeated-Characters
    • 1153.String-Transforms-Into-Another-String
    • 12.Integer-to-Roman
    • 125.Valid-Palindrome
    • 151.Reverse-Words-in-a-String
    • 161.One-Edit-Distance
    • 165.Compare-Version-Numbers
    • 168.Excel-Sheet-Column-Title
    • 171.Excel-Sheet-Column-Number
    • 205.Isomorphic-Strings
    • 214.Shortest-Palindrome
    • 242.Valid-Anagram
    • 3.Longest-Substring-Without-Repeating-Characters
    • 344.Reverse-String
    • 415.Add-Strings
    • 43.Multiply-Strings
    • 443.String-Compression
    • 459.Repeated-Substring-Pattern
    • 482.License-Key-Formatting
    • 5.Longest-Palindromic-Substring
    • 556.Next-Greater-Element-III
    • 557.Reverse-Words-in-a-String-III
    • 567.Permutation-in-String
    • 640.Solve-the-Equation
    • 68.Text-Justification
    • 726.Number-of-Atoms
    • 736.Parse-Lisp-Expression
    • 767.Reorganize-String
    • 784.Letter-Case-Permutation
    • 792.Number-of-Matching-Subsequences
    • 809.Expressive-Words
    • 819.Most-Common-Word
    • 833.Find-And-Replace-in-String
  • Toposort
    • 1136.Parallel-Courses
    • 207.Course-Schedule
    • 210.Course-Schedule-II
    • 269.Alien-Dictionary
    • 444.Sequence-Reconstruction
    • 468.Validate-IP-Address
    • Topological Sorting
  • Trie Tree
    • 1032.Stream-of-Characters
    • 1268.Search-Suggestions-System
    • [208.Implement-Trie-(Prefix-Tree)](Trie-Tree/208.Implement-Trie-(Prefix-Tree).md)
    • 336.Palindrome-Pairs
  • Two Pointers
    • 1004.Max-Consecutive-Ones-III
    • 1099.Two-Sum-Less-Than-K
    • 159.Longest-Substring-with-At-Most-Two-Distinct-Characters
    • 167.Two-Sum-II---Input-array-is-sorted
    • 26.Remove-Duplicates-from-Sorted-Array
    • 27.Remove-Element
    • 340.Longest-Substring-with-At-Most-K-Distinct-Characters
    • 42.Trapping-Rain-Water
    • 647.Palindromic-Substrings
    • 680.Valid-Palindrome-II
    • 75.Sort-Colors
    • 76.Minimum-Window-Substring
    • 88.Merge-Sorted-Array
    • Sort Colors Ii
  • Union Find
    • 1168.Optimize-Water-Distribution-in-a-Village
    • 803.Bricks-Falling-When-Hit
    • 924.Minimize-Malware-Spread
    • 947.Most-Stones-Removed-with-Same-Row-or-Column
Powered by GitBook
On this page
  • 809. Expressive Words
  • 题目地址
  • 题目描述
  • 代码
  • Approach #1 Run Length Encoding

Was this helpful?

  1. String

809.Expressive-Words

Previous792.Number-of-Matching-SubsequencesNext819.Most-Common-Word

Last updated 4 years ago

Was this helpful?

809. Expressive Words

题目地址

题目描述

Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii".  In these strings like "heeellooo", we have groups of adjacent letters that are all the same:  "h", "eee", "ll", "ooo".

For some given string S, a query word is stretchy if it can be made to be equal to S by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is 3 or more.

For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has size less than 3.  Also, we could do another extension like "ll" -> "lllll" to get "helllllooo".  If S = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = S.

Given a list of query words, return the number of words that are stretchy. 

Example:
Input: 
S = "heeellooo"
words = ["hello", "hi", "helo"]
Output: 1
Explanation: 
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.

Notes:
0 <= len(S) <= 100.
0 <= len(words) <= 100.
0 <= len(words[i]) <= 100.
S and all words in words consist only of lowercase letters

代码

Approach #1 Run Length Encoding

Time: O(QK) && Space: O(K)

where Q is the length of words (at least 1), and K is the maximum length of a word.)

class Solution {
  public int expressiveWords(String S, String[] words) {
    RLE R = new RLE(S);
    int ans = 0;

    search: for (String word: words) {
      RLE R2 = new RLE(word);
      if (!R.key.equals(R2.key)) continue;
      for (int i = 0; i < R.counts.size(); i++) {
        int c1 = R.counts.get(i);
        int c2 = R2.counts.get(i);
        if (c1 < 3 && c1 != c2 || c1 < c3) {
          continue search;
        }
      }
      ans++;
    }

    return ans;
  }
}

class RLE {
  String key;
  List<Integer> counts;

  public RLE(String S) {
    StringBuilder sb = new StringBuilder();
    counts = new ArrayList();

    char[] ca = S.toCharArray();
    int N = ca.length;
    int prev = -1;
    for (int i = 0; i < N; i++) {
      if (i == N - 1 || ca[i] != ca[i+1]) {
        sb.append(ca[i]);
        counts.add(i - prev);
        prev = i;
      }
    }
    key = sb.toString();
  }
}
https://leetcode.com/problems/expressive-words/