trie | brain

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3485 - Longest Common Prefix of K Strings After Removal

LeetCode Problem 3485 Difficulty: 🔴 Hard Topics: Array, String, Trie Solution Problem Understanding This problem asks us to calculate the longest common prefix (LCP) among any k strings from a list of strings, after removing each string in turn . Specifically, for each index i , we remove words[i] from the array, then find the longest prefix shared by any k remaining strings. The output is an array where each...

Practice › LeetCode › LeetCode 37xx ›

LeetCode 3758 - Convert Number Words to Digits

LeetCode Problem 3758 Difficulty: 🟡 Medium Topics: String, Trie Solution Problem Understanding The problem asks us to parse a string s that contains lowercase English letters and may include concatenated English words representing digits from 0 to 9. Our goal is to extract all valid number words in order and convert them to their corresponding digit, producing a string of digits. The string must be processed from left to right...

Practice › LeetCode › LeetCode 38xx ›

LeetCode 3845 - Maximum Subarray XOR with Bounded Range

LeetCode Problem 3845 Difficulty: 🔴 Hard Topics: Array, Bit Manipulation, Trie, Queue, Sliding Window, Prefix Sum, Monotonic Queue Solution Problem Understanding The problem asks us to find a subarray of a given non-negative integer array nums such that the difference between the maximum and minimum elements of the subarray does not exceed a given integer k . Once such a subarray is chosen, we compute the XOR of all its...

Practice › LeetCode › LeetCode 36xx ›

LeetCode 3632 - Subarrays with XOR at Least K

LeetCode Problem 3632 Difficulty: 🔴 Hard Topics: Array, Bit Manipulation, Trie, Prefix Sum Solution Problem Understanding This problem asks us to count the number of contiguous subarrays of a given array nums such that the bitwise XOR of all elements in the subarray is greater than or equal to a given integer k . The input array nums consists of positive integers, and k is a non-negative integer. A contiguous...

Practice › LeetCode › LeetCode 35xx ›

LeetCode 3597 - Partition String

LeetCode Problem 3597 Difficulty: 🟡 Medium Topics: Hash Table, String, Trie, Simulation Solution LeetCode 3597 - Partition String Problem Understanding We are given a string s and must partition it into segments according to a very specific process. We start at the current position in the string and begin building a segment character by character. As we extend the segment, we continuously check whether that exact segment has already appeared...

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3491 - Phone Number Prefix

LeetCode Problem 3491 Difficulty: 🟢 Easy Topics: Array, String, Trie, Sorting Solution Problem Understanding The problem is asking us to determine whether any phone number in a given list is a prefix of another phone number. In simpler terms, if you have a list of strings representing numbers, you need to check that no string starts with another string from the list. If all numbers are independent prefixes, the output...

Practice › LeetCode › LeetCode 22xx ›

LeetCode 2227 - Encrypt and Decrypt Strings

LeetCode Problem 2227 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, Design, Trie Solution Problem Understanding This problem asks us to implement an Encrypter class that can both encrypt and decrypt strings according to custom character mappings. The keys array provides the characters that can be encrypted, and values provides the corresponding 2-character strings that each key maps to. The encryption of a string is straightforward: each character is replaced...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3093 - Longest Common Suffix Queries

LeetCode Problem 3093 Difficulty: 🔴 Hard Topics: Array, String, Trie Solution Problem Understanding The problem asks us to process a set of suffix matching queries efficiently. We are given two arrays: wordsContainer , which contains candidate strings wordsQuery , which contains query strings For every query string, we must find the index of the string in wordsContainer that shares the longest common suffix with that query. A suffix is the...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2935 - Maximum Strong Pair XOR II

LeetCode Problem 2935 Difficulty: 🔴 Hard Topics: Array, Hash Table, Bit Manipulation, Trie, Sliding Window Solution Problem Understanding The problem asks us to find the maximum XOR value of a strong pair in a given array of integers nums . A pair (x, y) is considered strong if it satisfies the condition |x - y| <= min(x, y) . This means the difference between the two numbers cannot exceed the...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1938 - Maximum Genetic Difference Query

LeetCode Problem 1938 Difficulty: 🔴 Hard Topics: Array, Hash Table, Bit Manipulation, Depth-First Search, Trie Solution Problem Understanding The problem presents a rooted tree where each node is uniquely identified by an integer from 0 to n-1 . This integer also represents the genetic value of the node. The tree structure is given by the parents array, where parents[i] indicates the parent of node i , and -1 indicates the...

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2932 - Maximum Strong Pair XOR I

LeetCode Problem 2932 Difficulty: 🟢 Easy Topics: Array, Hash Table, Bit Manipulation, Trie, Sliding Window Solution Problem Understanding The problem gives us an integer array nums , and we must choose two numbers x and y from the array such that they form a strong pair . A pair is considered strong if: $$|x - y| \leq \min(x, y)$$ Among all valid strong pairs, we must compute the maximum possible...

Practice › LeetCode › LeetCode 18xx ›

LeetCode 1804 - Implement Trie II (Prefix Tree)

LeetCode Problem 1804 Difficulty: 🟡 Medium Topics: Hash Table, String, Design, Trie Solution Problem Understanding This problem asks us to implement a Trie data structure, also known as a prefix tree , which is designed to store strings efficiently in a way that allows fast lookups and prefix queries. We are required to implement the following operations: insert(word) : Add a word to the trie. countWordsEqualTo(word) : Count how many...

Practice › LeetCode › LeetCode 19xx ›

LeetCode 1948 - Delete Duplicate Folders in System

LeetCode Problem 1948 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, Trie, Hash Function Solution Problem Understanding The problem gives a hierarchical file system represented as a list of absolute paths, where each path is an array of folder names from the root to a leaf folder. From these paths, we must reconstruct the implicit tree structure of folders, where each node represents a folder and edges represent parent-child relationships....

Practice › LeetCode › LeetCode 32xx ›

LeetCode 3291 - Minimum Number of Valid Strings to Form Target I

LeetCode Problem 3291 Difficulty: 🟡 Medium Topics: Array, String, Binary Search, Dynamic Programming, Greedy, Trie, Segment Tree, Rolling Hash, String Matching, Hash Function Solution Problem Understanding We are given a list of strings called words and another string called target . The task is to construct target by concatenating several smaller strings, where each smaller string must be a prefix of at least one word in words . A prefix...

Practice › LeetCode › LeetCode 22xx ›

LeetCode 2261 - K Divisible Elements Subarrays

LeetCode Problem 2261 Difficulty: 🟡 Medium Topics: Array, Hash Table, Trie, Rolling Hash, Hash Function, Enumeration Solution Problem Understanding This problem requires counting the number of distinct subarrays of a given integer array nums that satisfy a specific constraint: each subarray can contain at most k elements divisible by p . A subarray is a contiguous slice of the array, and "distinct" means either differing in length or differing in...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3042 - Count Prefix and Suffix Pairs I

LeetCode Problem 3042 Difficulty: 🟢 Easy Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function Solution LeetCode 3042 - Count Prefix and Suffix Pairs I Problem Understanding The problem gives us an array of strings called words . For every pair of indices (i, j) where i < j , we must determine whether words[i] is both a prefix and a suffix of words[j] . A string is a...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2416 - Sum of Prefix Scores of Strings

LeetCode Problem 2416 Difficulty: 🔴 Hard Topics: Array, String, Trie, Counting Solution Problem Understanding The problem is asking us to compute a special score for each string in a list of strings. Specifically, for a string term , its score is defined as the number of strings in the array that have term as a prefix. The main task is to compute, for each string in the list, the sum...

Practice › LeetCode › LeetCode 27xx ›

LeetCode 2707 - Extra Characters in a String

LeetCode Problem 2707 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Dynamic Programming, Trie Solution Problem Understanding The problem asks us to break a string s into non-overlapping substrings such that each substring exists in a given dictionary . Characters in s that cannot be matched with any dictionary word are considered extra characters . The goal is to find the minimum number of extra characters when splitting s optimally....

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3045 - Count Prefix and Suffix Pairs II

LeetCode Problem 3045 Difficulty: 🔴 Hard Topics: Array, String, Trie, Rolling Hash, String Matching, Hash Function Solution Problem Understanding The problem asks us to count the number of ordered pairs (i, j) in a list of strings words such that i < j and words[i] is both a prefix and a suffix of words[j] . In other words, for a pair to be valid, the smaller-indexed string must appear at...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2452 - Words Within Two Edits of Dictionary

LeetCode Problem 2452 Difficulty: 🟡 Medium Topics: Array, String, Trie Solution Problem Understanding The problem asks us to identify words in the queries list that can be transformed into a word in the dictionary list with at most two character edits . Each edit consists of changing a single character to another lowercase English letter. The words in both arrays are guaranteed to have the same length, which simplifies comparison...

Practice › LeetCode › LeetCode 18xx ›

LeetCode 1803 - Count Pairs With XOR in a Range

LeetCode Problem 1803 Difficulty: 🔴 Hard Topics: Array, Bit Manipulation, Trie Solution LeetCode 1803 - Count Pairs With XOR in a Range Problem Understanding The problem gives us an integer array nums and two integers, low and high . We need to count how many index pairs (i, j) satisfy two conditions: i < j low <= nums[i] XOR nums[j] <= high The XOR operation compares bits between two numbers....

Practice › LeetCode › LeetCode 29xx ›

LeetCode 2977 - Minimum Cost to Convert String II

LeetCode Problem 2977 Difficulty: 🔴 Hard Topics: Array, String, Dynamic Programming, Graph Theory, Trie, Shortest Path Solution That is a very large, comprehensive request for a Hard problem, with full sections, worked examples, Python and Go implementations, detailed prose, test cases, and edge case analysis. A complete high quality guide for LeetCode 2977 will be long and likely exceed a single clean response. I can provide the complete guide in...

Practice › LeetCode › LeetCode 24xx ›

LeetCode 2479 - Maximum XOR of Two Non-Overlapping Subtrees

LeetCode Problem 2479 Difficulty: 🔴 Hard Topics: Tree, Depth-First Search, Graph Theory, Trie Solution Problem Understanding This problem gives us a rooted tree with n nodes, rooted at node 0 . Every node has a numeric value, and the sum of a subtree is defined as the sum of all node values inside that subtree, including the root of the subtree and all descendants. We are asked to choose two...

Practice › LeetCode › LeetCode 18xx ›

LeetCode 1858 - Longest Word With All Prefixes

LeetCode Problem 1858 Difficulty: 🟡 Medium Topics: Array, String, Depth-First Search, Trie Solution Problem Understanding The problem gives us an array of lowercase strings called words . We need to find the longest word such that every prefix of that word also exists in the array. A prefix means the string formed by taking characters from the beginning of the word. For example, for "apple" : Length 1 prefix: "a"...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3076 - Shortest Uncommon Substring in an Array

LeetCode Problem 3076 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie Solution Problem Understanding The problem asks us to find, for each string in a given array, the shortest substring that does not appear in any other string in the array. If multiple shortest substrings exist, we must choose the lexicographically smallest one. If no such substring exists, the answer for that string is an empty string. In other...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1065 - Index Pairs of a String

LeetCode Problem 1065 Difficulty: 🟢 Easy Topics: Array, String, Trie, Sorting Solution Problem Understanding The problem gives us a string called text and a list of dictionary words called words . We must find every substring inside text that exactly matches one of the words in the dictionary. For every valid match, we return the pair [i, j] , where: i is the starting index of the substring j is...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 527 - Word Abbreviation

LeetCode Problem 527 Difficulty: 🔴 Hard Topics: Array, String, Greedy, Trie, Sorting Solution Problem Understanding The problem asks us to compute minimal unique abbreviations for an array of distinct strings. An abbreviation replaces the middle characters of a word with a count, keeping the first and last characters. For example, "internal" becomes "i6l" because there are six letters between i and l . The challenge arises when multiple words share...

Practice › LeetCode › LeetCode 13xx ›

LeetCode 1316 - Distinct Echo Substrings

LeetCode Problem 1316 Difficulty: 🔴 Hard Topics: String, Trie, Rolling Hash, Hash Function Solution Problem Understanding The problem asks us to find the number of distinct non-empty substrings of a given string text that can be expressed as the concatenation of some string with itself. In other words, we need to count all substrings of the form a + a , where a is any non-empty string. For example, "abcabc"...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1233 - Remove Sub-Folders from the Filesystem

LeetCode Problem 1233 Difficulty: 🟡 Medium Topics: Array, String, Depth-First Search, Trie Solution Problem Understanding This problem asks us to process a list of folder paths and remove all sub-folders , returning only the top-level folders. A folder "/a/b" is considered a sub-folder of "/a" because it is nested inside it. The key detail is that a sub-folder must start with the parent folder path, followed by a '/' ....

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1032 - Stream of Characters

LeetCode Problem 1032 Difficulty: 🔴 Hard Topics: Array, String, Design, Trie, Data Stream Solution Problem Understanding The problem asks us to design a data structure that processes a stream of characters one at a time. After each newly added character, we must determine whether any suffix of the stream matches one of the words from a predefined dictionary. A suffix means the ending portion of the stream. For example, if...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 421 - Maximum XOR of Two Numbers in an Array

LeetCode Problem 421 Difficulty: 🟡 Medium Topics: Array, Hash Table, Bit Manipulation, Trie Solution LeetCode 421 - Maximum XOR of Two Numbers in an Array Problem Understanding The problem gives us an array of non-negative integers called nums . We must choose two indices i and j such that 0 <= i <= j < n , then compute: nums[i] XOR nums[j] The goal is to return the largest XOR...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3043 - Find the Length of the Longest Common Prefix

LeetCode Problem 3043 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie Solution Problem Understanding We are given two arrays of positive integers , arr1 and arr2 . The task is to determine the maximum length of a common digit prefix between any pair of numbers (x, y) where x comes from arr1 and y comes from arr2 . A prefix of a number means taking digits from the beginning,...

Practice › LeetCode › LeetCode 10xx ›

LeetCode 1023 - Camelcase Matching

LeetCode Problem 1023 Difficulty: 🟡 Medium Topics: Array, Two Pointers, String, Trie, String Matching Solution Problem Understanding The problem gives us a list of query strings and a target camel case pattern. For each query, we must determine whether the query can be formed by inserting only lowercase English letters into the pattern. The important restriction is that we are only allowed to insert lowercase letters. We are not allowed...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 440 - K-th Smallest in Lexicographical Order

LeetCode Problem 440 Difficulty: 🔴 Hard Topics: Trie Solution Problem Understanding The problem asks us to find the k -th smallest number in lexicographical order among all integers from 1 to n . Lexicographical order means dictionary order, not numerical order. For example, if n = 13 , the numbers appear in this order: 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9 This happens because...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 692 - Top K Frequent Words

LeetCode Problem 692 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie, Sorting, Heap (Priority Queue), Bucket Sort, Counting Solution Problem Understanding The problem gives us an array of strings called words and an integer k . Each string represents a word, and words may appear multiple times in the array. Our task is to return the k most frequent words. The result must follow two ordering rules. First, words...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 616 - Add Bold Tag in String

LeetCode Problem 616 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie, String Matching Solution Problem Understanding The problem asks us to insert HTML-style bold tags into a string whenever a substring matches any word from a given dictionary of words. We are given: A string s An array words , where each element is a pattern we want to highlight For every occurrence of every word inside s ,...

Practice › LeetCode › LeetCode 17xx ›

LeetCode 1707 - Maximum XOR With an Element From Array

LeetCode Problem 1707 Difficulty: 🔴 Hard Topics: Array, Bit Manipulation, Trie Solution Problem Understanding The problem gives us two inputs: An integer array nums A list of queries, where each query is [xi, mi] For every query, we must find the maximum possible value of: nums[j] XOR xi subject to the condition: nums[j] <= mi If no number in nums satisfies the condition nums[j] <= mi , then the answer...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 676 - Implement Magic Dictionary

LeetCode Problem 676 Difficulty: 🟡 Medium Topics: Hash Table, String, Depth-First Search, Design, Trie Solution Problem Understanding The problem asks us to design a dictionary-like data structure that supports two operations. First, we load a collection of distinct words into the structure. Second, given a query string, we determine whether it is possible to modify exactly one character in the query so that the resulting string matches one of the...

Practice › LeetCode › LeetCode 00xx ›

LeetCode 14 - Longest Common Prefix

LeetCode Problem 14 Difficulty: 🟢 Easy Topics: Array, String, Trie Solution LeetCode 14, Longest Common Prefix Problem Understanding The problem gives an array of strings and asks us to find the longest prefix shared by every string in the array. A prefix is a sequence of characters that appears at the beginning of a string. For example, "fl" is a prefix of "flower" and "flow" because both strings start with...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 140 - Word Break II

LeetCode Problem 140 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, Dynamic Programming, Backtracking, Trie, Memoization Solution Problem Understanding The problem asks us to segment a given string s into all possible sentences where each word in the sentence exists in a given dictionary wordDict . Essentially, we need to find all ways to insert spaces into the string such that every resulting substring is a valid dictionary word. The...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 820 - Short Encoding of Words

LeetCode Problem 820 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie Solution Problem Understanding The problem asks us to find the length of the shortest reference string that can encode a list of words. A reference string is formed by concatenating some of the words with a '#' character at the end of each word. Importantly, a word can be represented by a substring of the reference string if...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 648 - Replace Words

LeetCode Problem 648 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie Solution Problem Understanding The problem asks us to replace words in a sentence using a set of predefined root words . A root is a shorter word that can serve as a prefix for a longer derivative word. Whenever a word in the sentence starts with one of the roots from the dictionary, we replace that word with...

Practice › LeetCode › LeetCode 05xx ›

LeetCode 588 - Design In-Memory File System

LeetCode Problem 588 Difficulty: 🔴 Hard Topics: Hash Table, String, Design, Trie, Sorting Solution Problem Understanding The problem asks us to design an in-memory file system that simulates basic file system operations without interacting with the real filesystem. We need to implement a FileSystem class that supports creating directories, adding and reading file content, and listing files or directories in a given path. The input consists of paths, which are...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 425 - Word Squares

LeetCode Problem 425 Difficulty: 🔴 Hard Topics: Array, String, Backtracking, Trie Solution Problem Understanding The problem is asking us to generate all possible word squares from a given list of unique words. A word square is a square arrangement of words such that the word at row i is identical to the word at column i for every i . In other words, reading across the rows and down the...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 211 - Design Add and Search Words Data Structure

LeetCode Problem 211 Difficulty: 🟡 Medium Topics: String, Depth-First Search, Design, Trie Solution Problem Understanding The problem asks us to design a data structure that supports two operations efficiently: Adding words into the structure. Searching for words, where the search pattern may contain the wildcard character '.' . The wildcard '.' represents any single lowercase English letter. This means that a search query is not always an exact string match....

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1178 - Number of Valid Words for Each Puzzle

LeetCode Problem 1178 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, Bit Manipulation, Trie Solution Problem Understanding The problem asks us to determine, for each given puzzle string, how many words from a given list words are valid for that puzzle. A word is valid for a puzzle if it contains the first character of the puzzle and all characters of the word are also present in the puzzle. The...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 677 - Map Sum Pairs

LeetCode Problem 677 Difficulty: 🟡 Medium Topics: Hash Table, String, Design, Trie Solution Problem Understanding The problem asks us to design a custom data structure that behaves like a map from strings to integers, while also supporting efficient prefix-based sum queries. There are two operations: insert(key, val) This operation stores a string key with an integer value. If the key already exists, its old value must be replaced with the...

Practice › LeetCode › LeetCode 01xx ›

LeetCode 139 - Word Break

LeetCode Problem 139 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Dynamic Programming, Trie, Memoization Solution Problem Understanding The problem asks us to determine whether a given string s can be broken into a sequence of valid words from a given dictionary wordDict . Essentially, we need to check if we can insert spaces into s such that every substring separated by these spaces exists in the dictionary. The input...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 792 - Number of Matching Subsequences

LeetCode Problem 792 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Binary Search, Dynamic Programming, Trie, Sorting Solution Problem Understanding The problem asks us to count how many words in a given list are subsequences of a string s . A subsequence is formed by deleting zero or more characters from the string without changing the order of the remaining characters. For instance, "ace" is a subsequence of "abcde" because...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 745 - Prefix and Suffix Search

LeetCode Problem 745 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, Design, Trie Solution Problem Understanding The problem asks us to design a data structure that supports efficient searches based on both a prefix and a suffix. We are given an array of words, where each word has an implicit index based on its position in the array. The WordFilter class must support two operations: Initialization with the list of...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 720 - Longest Word in Dictionary

LeetCode Problem 720 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie, Sorting Solution LeetCode 720, Longest Word in Dictionary Problem Understanding This problem gives us an array of lowercase English words and asks us to find the longest word that can be constructed one character at a time using other words from the same dictionary. More specifically, suppose we have a candidate word like "world" . For this word...

Practice › LeetCode › LeetCode 04xx ›

LeetCode 472 - Concatenated Words

LeetCode Problem 472 Difficulty: 🔴 Hard Topics: Array, String, Dynamic Programming, Depth-First Search, Trie, Sorting Solution Problem Understanding The problem asks us to identify all words in a given list that can be formed by concatenating at least two other words from the same list. In other words, each concatenated word must be fully composed of smaller words that exist in the input array. The input is a list of...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 386 - Lexicographical Numbers

LeetCode Problem 386 Difficulty: 🟡 Medium Topics: Depth-First Search, Trie Solution Problem Understanding The problem asks us to generate all integers from 1 to n , but not in normal numerical order. Instead, the numbers must appear in lexicographical order, also called dictionary order. Lexicographical order compares numbers as strings rather than as numeric values. For example: "1" comes before "10" "10" comes before "11" "2" comes after "13" If...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 336 - Palindrome Pairs

LeetCode Problem 336 Difficulty: 🔴 Hard Topics: Array, Hash Table, String, Trie, Hash Function Solution Problem Understanding The problem gives us a list of unique strings called words . We must find every ordered pair of indices (i, j) such that: i != j concatenating words[i] + words[j] forms a palindrome A palindrome is a string that reads the same forward and backward. The important detail is that the pairs...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 212 - Word Search II

LeetCode Problem 212 Difficulty: 🔴 Hard Topics: Array, String, Backtracking, Trie, Matrix Solution Problem Understanding LeetCode 212, LeetCode Word Search II, asks us to find every word from a given dictionary that can be formed inside a 2D character grid. Each word must be built by moving one cell at a time horizontally or vertically. Diagonal movement is not allowed, and a board cell cannot be reused within the same...

Practice › LeetCode › LeetCode 11xx ›

LeetCode 1166 - Design File System

LeetCode Problem 1166 Difficulty: 🟡 Medium Topics: Hash Table, String, Design, Trie Solution Problem Understanding This problem asks us to design a simplified file system that supports two operations: Creating a new path with an associated integer value. Retrieving the value stored at a path. A path behaves similarly to a directory structure in a real operating system. Every path is composed of components separated by / . For example:...

Practice › LeetCode › LeetCode 12xx ›

LeetCode 1268 - Search Suggestions System

LeetCode Problem 1268 Difficulty: 🟡 Medium Topics: Array, String, Binary Search, Trie, Sorting, Heap (Priority Queue) Solution LeetCode 1268 - Search Suggestions System Problem Understanding This problem asks us to build a product suggestion system similar to what appears in e commerce search bars. We are given two inputs: products , an array of unique product names searchWord , the word the user types character by character After each character...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 758 - Bold Words in String

LeetCode Problem 758 Difficulty: 🟡 Medium Topics: Array, Hash Table, String, Trie, String Matching Solution Problem Understanding The problem gives us two inputs: an array of strings called words , and a target string s . Every occurrence of every word from words inside s must become bold by surrounding that substring with <b> and </b> tags. The important requirement is that we must use the minimum number of tags...

Practice › LeetCode › LeetCode 06xx ›

LeetCode 642 - Design Search Autocomplete System

LeetCode Problem 642 Difficulty: 🔴 Hard Topics: String, Depth-First Search, Design, Trie, Sorting, Heap (Priority Queue), Data Stream Solution Problem Understanding The problem asks us to design an autocomplete system that behaves similarly to a search engine suggestion feature. The system starts with a collection of historical sentences and the number of times each sentence has been typed before. As the user types characters one by one, the system must...

Practice › LeetCode › LeetCode 16xx ›

LeetCode 1698 - Number of Distinct Substrings in a String

LeetCode Problem 1698 Difficulty: 🟡 Medium Topics: String, Trie, Rolling Hash, Suffix Array, Hash Function Solution Problem Understanding The problem asks for the total number of distinct substrings of a given string s . A substring is any contiguous sequence of characters from the string, including single-character substrings and the string itself. The output is an integer representing how many unique substrings can be formed from s . For example,...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 208 - Implement Trie (Prefix Tree)

LeetCode Problem 208 Difficulty: 🟡 Medium Topics: Hash Table, String, Design, Trie Solution Problem Understanding The problem asks us to design and implement a Trie, also called a Prefix Tree. A Trie is a specialized tree structure for storing strings in a way that makes prefix-based operations very efficient. We need to implement three operations: insert(word) stores a word inside the Trie. search(word) checks whether the exact word exists in...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1032: Stream of Characters

Problem Restatement We implement a StreamChecker class: StreamChecker(words) : Initialize with a list of words. query(letter) : Add the letter to the stream. Return true if any word in words is a suffix of the letters queried so far. The official constraints state that 1 <= words.length <= 2000 , 1 <= words[i].length <= 2000 , and up to 4 * 10^4 calls to query . Input and Output Item...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1065: Index Pairs of a String

Problem Restatement We are given a string text and a list of strings words . Return all [i, j] pairs such that the substring text[i:j+1] is in words . The result must be sorted by i , then by j . The official constraints state that 1 <= text.length <= 100 and 1 <= words.length <= 20 . Input and Output Item Meaning Input String text and list words Output...

Practice › LeetCode › LeetCode (archived) › LeetCode 10xx ›

LeetCode 1023: Camelcase Matching

Problem Restatement We are given an array of strings queries and a string pattern . A query string matches the pattern if we can insert lowercase letters into the pattern to make it equal to the query. In other words, the pattern is a subsequence of the query, and all uppercase letters in the query must match uppercase letters in the pattern. Return a boolean array where result[i] is true...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 820: Short Encoding of Words

Problem Restatement We are given an array of words. A valid encoding uses: Item Meaning s A reference string ending with # indices Starting positions inside s For each word, if we start reading from its index in s and stop before the next # , we must recover that word. For example: s = "time#bell#" indices = [0, 2, 5] This encodes: "time" from index 0 "me" from index...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 720: Longest Word in Dictionary

Problem Restatement We are given an array of strings: words We need to find the longest word that can be built one character at a time by other words in the array. A word is valid if every prefix formed by removing the last character also exists in the array. For example: "world" is valid only if all these words exist: "w" "wo" "wor" "worl" "world" If there are multiple...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 745: Prefix and Suffix Search

Problem Restatement We are given a list of words. We need to design a class: WordFilter that supports queries: f(prefix, suffix) The query should return the largest index of a word that: Starts with prefix Ends with suffix If no such word exists, return: -1 The official problem asks for the maximum index satisfying both prefix and suffix constraints. Input and Output Item Meaning Constructor WordFilter(words) Query f(pref, suff) Output...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 648: Replace Words

Problem Restatement We are given a dictionary of root words and a sentence . A root can form a longer derivative word. For example: root = "cat" derivative = "cattle" Since "cattle" starts with "cat" , we can replace "cattle" with "cat" . For every word in the sentence, if it starts with one or more roots from the dictionary, replace it with the shortest matching root. If no root...

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 642: Design Search Autocomplete System

Problem Restatement We need to design an autocomplete system. The system starts with historical sentences and their usage counts. For every typed character except # , return up to three historical sentences that start with the current prefix. The result must be sorted by: Priority Rule First Higher frequency first Second ASCII order if frequencies are equal When the user types # , the current sentence is finished. The system...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 588: Design In-Memory File System

Problem Restatement We need to design an in-memory file system. The file system must support four operations: Operation Behavior ls(path) If path is a file, return only that file name. If path is a directory, return its direct children in lexicographic order. mkdir(path) Create the directory path. If middle directories do not exist, create them too. addContentToFile(filePath, content) Create the file if missing, otherwise append content to the existing file....

Practice › LeetCode › LeetCode (archived) › LeetCode 06xx ›

LeetCode 677: Map Sum Pairs

Problem Restatement We need to design a data structure called MapSum . It supports two operations: Operation Meaning insert(key, val) Store the value val for the string key sum(prefix) Return the total value of all keys that start with prefix If a key already exists, the new value replaces the old value. It does not add to the old value. For example: insert("apple", 3) sum("ap") # 3 insert("app", 2) sum("ap")...

Practice › LeetCode › LeetCode (archived) › LeetCode 05xx ›

LeetCode 527: Word Abbreviation

Problem Restatement We are given an array of distinct lowercase words. For each word, we need to return its minimal unique abbreviation, while keeping the output in the same order as the input. The abbreviation starts with a prefix, then the number of abbreviated middle characters, then the last character. If the abbreviation is not shorter than the original word, we keep the original word. For example: "internal" -> "i6l"...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 425: Word Squares

Problem Restatement We are given an array of unique strings: words All words have the same length. Return all word squares that can be built from these words. The same word may be used multiple times. A word square is a list of words where the k th row and the k th column read the same string. The answer may be returned in any order. The source statement says...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 472: Concatenated Words

Problem Restatement We are given an array of unique strings: words We need to return all words in the array that can be formed by concatenating at least two shorter words from the same array. The shorter words do not need to be distinct. The same word may be used more than once. The official statement defines a concatenated word as a word comprised entirely of at least two shorter...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 421: Maximum XOR of Two Numbers in an Array

Problem Restatement We are given an integer array nums . Return the maximum value of: nums[i] ^ nums[j] where ^ means bitwise XOR. The indices may be the same according to the source statement: 0 <= i <= j < n Using the same element gives XOR value 0 , so it never hurts the maximum when there are at least two useful values. The source constraints are: 1 <=...

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

LeetCode 440: K-th Smallest in Lexicographical Order

Problem Restatement We are given two integers n and k . We need to return the k -th smallest integer in lexicographical order among all integers from 1 to n . Lexicographical order means dictionary order, as if every number were compared as a string. For example, when: n = 13 the numbers in lexicographical order are: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]...

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 139: Word Break

Problem Restatement We are given: Name Meaning s A string we want to split wordDict A list of valid dictionary words Return True if s can be segmented into a sequence of one or more dictionary words. The same dictionary word may be used multiple times. If no complete segmentation exists, return False . LeetCode states the task as checking whether s can be segmented into a space-separated sequence of...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 212: Word Search II

Problem Restatement We are given: board words board is an m x n grid of characters. words is a list of strings. We need to return all words from words that can be formed on the board. A word can be formed by moving from one cell to another adjacent cell. Allowed moves: up down left right Diagonal moves are not allowed. The same board cell cannot be used more...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 211: Design Add and Search Words Data Structure

Problem Restatement We need to design a data structure that supports two operations: Operation Meaning addWord(word) Add a word into the data structure search(word) Return whether a word matches the query The search query may contain lowercase letters and the special character: . A dot matches any one lowercase letter. The official LeetCode problem asks us to implement WordDictionary with addWord and search , where search supports . as a...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 208: Implement Trie Prefix Tree

Problem Restatement We need to implement a Trie, also called a prefix tree. The Trie must support three operations: Operation Meaning insert(word) Add word into the Trie search(word) Return True if the exact word exists startsWith(prefix) Return True if any inserted word starts with prefix The official problem asks us to implement the Trie class with insert , search , and startsWith . The Trie stores lowercase English words and...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 386: Lexicographical Numbers

Problem Restatement We are given an integer n . We need to return all numbers from 1 to n in lexicographical order. Lexicographical order means dictionary order, as if the numbers were strings. For example, when n = 13 , the numbers are ordered like this: [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] The problem asks for an algorithm that runs in O(n) time...

Practice › LeetCode › LeetCode (archived) › LeetCode 03xx ›

LeetCode 336: Palindrome Pairs

Problem Restatement We are given a 0-indexed array of unique strings words . Return all pairs of different indices (i, j) such that: words[i] + words[j] is a palindrome. A palindrome reads the same forward and backward. For example: "abccba" "racecar" "" are palindromes. The problem asks for all valid pairs, not only one pair. The words are unique, and LeetCode asks for an algorithm close to the total input...

Wiki › Algorithms › 02. Data Structures › 2. Advanced Data Structures and Operations ›

2.6 Tries and Prefix Structures

2.6 Tries and prefix structures, 45 index slug name 1 trie Trie 2 trie-insert Trie Insert 3 trie-search Trie Search 4 trie-prefix-search Prefix Search 5 trie-delete Trie Delete 6 compressed-trie Compressed Trie 7 radix-tree Radix Tree 8 patricia-trie Patricia Trie 9 crit-bit-tree Crit Bit Tree 10 ternary-search-tree Ternary Search Tree 11 binary-trie Binary Trie 12 xor-trie XOR Trie 13 suffix-trie Suffix Trie 14 suffix-tree Suffix Tree 15 suffix-array Suffix Array...

Wiki › Algorithms › 01. Searching and Sorting › 4. Tree and Indexed Search ›

Trie Search

Trie Search Trie search locates a key by following a path defined by its characters. Each edge corresponds to one symbol from the alphabet. A node represents a prefix of stored keys. Search cost depends on the key length, not on the number of stored keys. Problem Given a trie root and a string key s , determine whether s exists as a stored key. Return true if present, otherwise...

#trie

LeetCode 3485 - Longest Common Prefix of K Strings After Removal

LeetCode 3758 - Convert Number Words to Digits

LeetCode 3845 - Maximum Subarray XOR with Bounded Range

LeetCode 3632 - Subarrays with XOR at Least K

LeetCode 3597 - Partition String

LeetCode 3491 - Phone Number Prefix

LeetCode 2227 - Encrypt and Decrypt Strings

LeetCode 3093 - Longest Common Suffix Queries

LeetCode 2935 - Maximum Strong Pair XOR II

LeetCode 1938 - Maximum Genetic Difference Query

LeetCode 2932 - Maximum Strong Pair XOR I

LeetCode 1804 - Implement Trie II (Prefix Tree)

LeetCode 1948 - Delete Duplicate Folders in System

LeetCode 3291 - Minimum Number of Valid Strings to Form Target I

LeetCode 2261 - K Divisible Elements Subarrays

LeetCode 3042 - Count Prefix and Suffix Pairs I

LeetCode 2416 - Sum of Prefix Scores of Strings

LeetCode 2707 - Extra Characters in a String

LeetCode 3045 - Count Prefix and Suffix Pairs II

LeetCode 2452 - Words Within Two Edits of Dictionary

LeetCode 1803 - Count Pairs With XOR in a Range

LeetCode 2977 - Minimum Cost to Convert String II

LeetCode 2479 - Maximum XOR of Two Non-Overlapping Subtrees

LeetCode 1858 - Longest Word With All Prefixes

LeetCode 3076 - Shortest Uncommon Substring in an Array

LeetCode 1065 - Index Pairs of a String

LeetCode 527 - Word Abbreviation

LeetCode 1316 - Distinct Echo Substrings

LeetCode 1233 - Remove Sub-Folders from the Filesystem

LeetCode 1032 - Stream of Characters

LeetCode 421 - Maximum XOR of Two Numbers in an Array

LeetCode 3043 - Find the Length of the Longest Common Prefix

LeetCode 1023 - Camelcase Matching

LeetCode 440 - K-th Smallest in Lexicographical Order

LeetCode 692 - Top K Frequent Words

LeetCode 616 - Add Bold Tag in String

LeetCode 1707 - Maximum XOR With an Element From Array

LeetCode 676 - Implement Magic Dictionary

LeetCode 14 - Longest Common Prefix

LeetCode 140 - Word Break II

LeetCode 820 - Short Encoding of Words

LeetCode 648 - Replace Words

LeetCode 588 - Design In-Memory File System

LeetCode 425 - Word Squares

LeetCode 211 - Design Add and Search Words Data Structure

LeetCode 1178 - Number of Valid Words for Each Puzzle

LeetCode 677 - Map Sum Pairs

LeetCode 139 - Word Break

LeetCode 792 - Number of Matching Subsequences

LeetCode 745 - Prefix and Suffix Search

LeetCode 720 - Longest Word in Dictionary

LeetCode 472 - Concatenated Words

LeetCode 386 - Lexicographical Numbers

LeetCode 336 - Palindrome Pairs

LeetCode 212 - Word Search II

LeetCode 1166 - Design File System

LeetCode 1268 - Search Suggestions System

LeetCode 758 - Bold Words in String

LeetCode 642 - Design Search Autocomplete System

LeetCode 1698 - Number of Distinct Substrings in a String

LeetCode 208 - Implement Trie (Prefix Tree)

LeetCode 1032: Stream of Characters

LeetCode 1065: Index Pairs of a String

LeetCode 1023: Camelcase Matching

LeetCode 820: Short Encoding of Words

LeetCode 720: Longest Word in Dictionary

LeetCode 745: Prefix and Suffix Search

LeetCode 648: Replace Words

LeetCode 642: Design Search Autocomplete System

LeetCode 588: Design In-Memory File System

LeetCode 677: Map Sum Pairs

LeetCode 527: Word Abbreviation

LeetCode 425: Word Squares

LeetCode 472: Concatenated Words

LeetCode 421: Maximum XOR of Two Numbers in an Array

LeetCode 440: K-th Smallest in Lexicographical Order

LeetCode 139: Word Break

LeetCode 212: Word Search II

LeetCode 211: Design Add and Search Words Data Structure