Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8e802c5

Browse files
authored
Batch-3/Neetcode-150/Added hints (neetcode-gh#3749)
1 parent4661f20 commit8e802c5

11 files changed

+291
-4
lines changed

‎articles/design-word-search-data-structure.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -226,10 +226,10 @@ class WordDictionary {
226226

227227
###Time & Space Complexity
228228

229-
* Time complexity: $O(1)$ for $addWord()$, $O(m * n)$ for $search()$.
229+
* Time complexity: $O(n)$ for $addWord()$, $O(m * n)$ for $search()$.
230230
* Space complexity: $O(m * n)$
231231

232-
>Where $m$ is the number of words added and $n$ is the length of thesearchstring.
232+
>Where $m$ is the number of words added and $n$ is the length of the string.
233233
234234
---
235235

@@ -631,7 +631,7 @@ class WordDictionary {
631631

632632
###Time & Space Complexity
633633

634-
* Time complexity: $O(n)$ for $addWord()$, $O(26 ^n)$ for $search()$.
634+
* Time complexity: $O(n)$ for $addWord()$, $O(n)$ for $search()$.
635635
* Space complexity: $O(t + n)$
636636

637637
>Where $n$ is the length of the string and $t$ is the total number of TrieNodes created in the Trie.

‎hints/combination-target-sum-ii.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n * (2^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute-force solution would be to create a <code>hash set</code>, which is used to detect duplicates, to get combinations without duplicates. Can you think of a better way without using a <code>hash set</code>? Maybe you should sort the input array and observe the recursive calls that are responsible for duplicate combinations.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use backtracking to generate all combinations whose sum equals the given target. When the input array contains duplicate elements, it may result in duplicate combinations. To avoid this, we can sort the array. Why does sorting help? Because as we traverse the array from left to right, we form combinations with the current element. By skipping duplicate elements, we ensure that the same combinations are not repeated for identical elements. How can you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We recursively traverse the given array starting at index <code>i</code>, with a variable <code>sum</code> representing the sum of the picked elements. We explore elements from <code>i</code> to the end of the array and extend the recursive path if adding the current element results in <code>sum <= target</code>. When we processed an element, we backtrack and proceed to the next distinct element, skipping any similar elements in the middle to avoid duplicate combinations.
30+
</p>
31+
</details>

‎hints/combination-target-sum.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,6 @@
2626
<detailsclass="hint-accordion">
2727
<summary>Hint 3</summary>
2828
<p>
29-
We recursivelyselect elements, increasing the<code>sum</code> and appending the element to the temporary list, which tracks the chosen elements in the current path. At each step, wehave the option to consider all elements inthe array, but we only proceedwith elementsthat, when added to<code>sum</code>, do not exceed the <code>target</code>. We iterate throughtheentire array at each step, choosing elements accordingly.
29+
We recursivelytraverse the array starting from index<code>i</code>. At each step, weselect an element from <code>i</code> to the end ofthe array. We extend the recursive pathwith elementswhere<code>sum <= target</code> after including that element. This creates multiple recursive paths, and we appendthecurrent list to the result whenever the base condition is met.
3030
</p>
3131
</details>
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n * (4^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the length of the input string.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
We can use a hash map to pair all the digits with their corresponding letters. Think of this as a decision tree, where at each step, we have a digit, and we select one of multiple characters to proceed to the next digit in the given string <code>digits</code>. Can you think of an algorithm to generate all combinations of strings?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use backtracking where we select a character and process it, then backtrack to process another character. We recursively iterate on the given string with index <code>i</code>. At each step, we consider the letters from the hash map that correspond to the digit at the <code>i-th</code> index. Can you think of the base condition to stop this recursive path?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We initialize an empty string that represents the choices of the characters throughout the current recursive path. When the index <code>i</code> reaches the end of the string, we add the current string to the result list and return.
30+
</p>
31+
</details>
Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time for each function call and <code>O(t + n)</code> space, where <code>n</code> is the length of the string and <code>t</code> is the total number of nodes created in the Trie.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute force solution would be to store each added word in a list and search linearly through the list for a word every time. This would be an <code>O(m * n)</code> solution, where <code>m</code> is the size of the list and <code>n</code> is the length of the string. Can you think of a better way? Maybe there is a tree-like data structure.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use a Trie to implement adding and searching for words efficiently. Adding a word follows the standard Trie insertion process. However, when searching for a word containing <code>'.'</code>, which can match any character, we need a different approach. Instead of directly matching, we consider all possible characters at the position of <code>'.'</code> and recursively check the rest of the word for each possibility. How would you implement it?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We traverse the word with index <code>i</code>, starting at the root of the Trie. For normal characters, we search as usual. When encountering a dot (<code>'.'</code>), we try all possible characters by recursively extending the search in each direction. If any path leads to a valid word, we return <code>true</code>; otherwise, we return <code>false</code>. Although we try all paths for a dot, the time complexity is still <code>O(n)</code> because there are at most two dots (<code>'.'</code>) in the word, making the complexity <code>O((26^2) * n)</code>.
30+
</p>
31+
</details>

‎hints/implement-prefix-tree.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n)</code> time for each function call and <code>O(t)</code> space, where <code>n</code> is the length of the given string and <code>t</code> is the total number of nodes created in the Trie.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A Trie is structured as a tree-like data structure where each node contains a hash map (or an array for fixed character sets) to store references to its child nodes, which represent characters. Each node also includes a boolean flag to indicate whether the current node marks the end of a valid word. The Trie starts with a root node that does not hold any character and serves as the entry point for all operations. The child nodes of the root and subsequent nodes represent unique characters from the words stored in the Trie, forming a hierarchical structure based on the prefixes of the words.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
To insert a word, we iterate through the characters of the word with index <code>i</code>, starting at the root of the Trie as the current node. If the current node already contains <code>word[i]</code>, we continue to the next character and move to the node that <code>word[i]</code> points to. If <code>word[i]</code> is not present, we create a new node for <code>word[i]</code> and continue the process until we reach the end of the word. We mark the boolean variable as true as it is the end of the inserted word.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
Searching for a word is similar to inserting, but instead of creating new nodes, we return <code>false</code> if we don't find a character in the path while iterating or if the end-of-word marker is not set to <code>true</code> when we reach the end of the word.
30+
</p>
31+
</details>

‎hints/n-queens.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n!)</code> time and <code>O(n^2)</code> space, where <code>n</code> is the size of the given square board.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A queen can move in <code>8</code> directions, and no two queens can be in the same row or column. This means we can place one queen per row or column. We iterate column-wise and try to place a queen in each column while ensuring no other queen exists in the same row, left diagonal, or left bottom diagonal. Can you think of a recursive algorithm to find all possible combinations?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use backtracking to traverse through the columns with index <code>c</code> while maintaining a board that represents the current state in the recursive path. We reach the base condition when <code>c == n</code> and we add a copy of the board to the result. How would you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We initialize an empty board and recursively go through each column. For each column, we check each cell to see if we can place a queen there. We use a function to check if the cell is suitable by iterating along the left directions and verifying if the same row, left diagonal, or left bottom diagonal are free. If it is possible, we place the queen on the board, move along the recursive path, and then backtrack by removing the queen to continue to the next cell in the column.
30+
</p>
31+
</details>

‎hints/palindrome-partitioning.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(n * (2^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the length of the input string.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
For a given string there are <code>2^n</code> possible partitions because at each index we have two decisions: we can either partition and start a new string, or continue without partitioning. Can you think of an algorithm to recursively traverse all combinations?
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use backtracking to recursively traverse the string with indices <code>j</code> (start of the current substring) and <code>i</code> (current iterating index). At each step, we either skip partitioning at the current index or, if the substring from <code>j</code> to <code>i</code> is a palindrome, make a partition, update <code>j = i + 1</code>, and start a new substring. The base condition to stop the recursion is when <code>j</code> reaches the end of the string. How do you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We start with <code>j = 0</code>, <code>i = 0</code> and a temporary list which stores the substrings from the partitions. Then we recursively iterate the string with the index <code>i</code>. At each step we apply the <code>2</code> decisions accordingly. At the base condition of the recursive path, we make a copy of the current partition list and add it to the result.
30+
</p>
31+
</details>

‎hints/search-for-word-ii.md

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(m * n * 4 * (3^(t-1)) + s)</code> time and <code>O(s)</code> space, where <code>m</code> is the number of rows, <code>n</code> is the number of columns, <code>t</code> is the maximum length of any word and <code>s</code> is the sum of the lengths of all the words.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
To search for a word in the grid, we can use backtracking by starting at each cell, simultaneously iterating through the word and matching the characters with the cells, recursively visiting the neighboring cells. However, if we are given a list of words and need to search for each one, it becomes inefficient to iterate through each word and run backtracking for each. Can you think of a better way? Perhaps a data structure could help with more efficient word search and insertion.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use a Trie to efficiently search for multiple words. After inserting all words into the Trie, we traverse the grid once. For each character in the grid, we check if it exists in the current Trie node. If not, we prune the search. If we encounter an "end of word" flag in the Trie node, we know a valid word has been found. But how can we add that word to the result list? Maybe you should think about what additional information you can store in the Trie node.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
When we insert a word into the Trie, we can store the word's index. Why? Because when we want to add the word to the result list after finding a valid word, we can easily add it using the index. After adding that word, we put <code>index = -1</code> as we shouldn't add the word multiple times to the result list. How can you implement this?
30+
</p>
31+
</details>
32+
33+
<br>
34+
<detailsclass="hint-accordion">
35+
<summary>Hint 4</summary>
36+
<p>
37+
We insert all the words into the Trie with their indices marked. Then, we iterate through each cell in the grid. At each cell, we start at the root of the Trie and explore all possible paths. As we traverse, we match characters in the cell with those in the Trie nodes. If we encounter the end of a word, we take the index at that node and add the corresponding word to the result list. Afterward, we unmark that index and continue exploring further paths.
38+
</p>
39+
</details>

‎hints/search-for-word.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution with <code>O(m * (4^n))</code> time and <code>O(n)</code> space, where <code>m</code> is the number of cells in the given <code>board</code> and <code>n</code> is the size of the given <code>word</code>.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
As we can start at any cell on the board, we can explore all paths from that cell. Can you think of an algorithm to do so? Also, you should consider a way to avoid visiting a cell that has already been visited in the current path.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use a hash set to avoid revisiting a cell in the current path by inserting the <code>(row, col)</code> of the visiting cell into the hash set and exploring all paths (four directions, as we can move to four neighboring cells) from that cell. Can you think of the base condition for this recursive path? Maybe you should consider the board boundaries, and also, we can extend a path if the character at the cell matches the character in the word.
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We can use backtracking, starting from each cell on the board with coordinates <code>(row, col)</code> and index <code>i</code> for the given word. We return false if <code>(row, col)</code> is out of bounds or if <code>board[row][col] != word[i]</code>. When <code>i</code> reaches the end of the word, we return true, indicating a valid path. At each step, we add <code>(row, col)</code> to a hash set to avoid revisiting cells. After exploring the four possible directions, we backtrack and remove <code>(row, col)</code> from the hash set.
30+
</p>
31+
</details>

‎hints/subsets-ii.md

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
<br>
2+
<detailsclass="hint-accordion">
3+
<summary>Recommended Time & Space Complexity</summary>
4+
<p>
5+
You should aim for a solution as good or better than <code>O(n * (2^n))</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array.
6+
</p>
7+
</details>
8+
9+
<br>
10+
<detailsclass="hint-accordion">
11+
<summary>Hint 1</summary>
12+
<p>
13+
A brute-force solution would involve creating a hash set and inserting every subset into it. Then, converting the hash set to a list and returning it. However, this approach would require extra space of <code>O(2^n)</code>. Can you think of a better way? Maybe you should sort the input array and observe which recusive calls are resposible to make duplicate subsets.
14+
</p>
15+
</details>
16+
17+
<br>
18+
<detailsclass="hint-accordion">
19+
<summary>Hint 2</summary>
20+
<p>
21+
We can use backtracking to generate subsets of an array. If the input contains duplicates, duplicate subsets may be created. To prevent this, we sort the array beforehand. For example, in <code>[1, 1, 2]</code>, sorting allows us to create subsets using the first <code>1</code> and skip the second <code>1</code>, ensuring unique subsets. How can you implement this?
22+
</p>
23+
</details>
24+
25+
<br>
26+
<detailsclass="hint-accordion">
27+
<summary>Hint 3</summary>
28+
<p>
29+
We start by sorting the input array. Then, we recursively iterate through the array from left to right, extending recursive paths by including or excluding each element. To avoid duplicate subsets, we skip an element if it is the same as the previous one. Finally, we return the generated subsets as a list.
30+
</p>
31+
</details>

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp