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

Commit35963c9

Browse files
add perform-string-shifts article (#4977)
* add maximum-distance-in-arrays article* fix article* fix csharp method signature* fix wiggle-sort python heap solution* add confusing-number.md article* Update explanation of L in complexity analysisClarify the definition of L in terms of n.* Fix logarithm notation in complexity sectionUpdated logarithm notation in complexity explanation.* Fix LaTeX formatting for logarithm in documentation* add perform-string-shifts article* add one-edit-distance article* fix one-edit-dsitance article* add reverse-words-in-a-string-ii.md article* fix typo maximu-distance-in-arrays.md* fix typo reverse-words-in-a-string-ii.md* add shortest-way-to-form-string.md article* add longest-substring-with-at-most-k-distinct-characters.md article* add max-consecutive-ones-ii.md article* add find-k-length-substrings-with-no-repeated-characters.md article* add find-anagram-mappings.md article* fix latex styling find-anagram-mappings.md* add palindrome-permutation.md article* add sentence-similarity.md article* add single-row-keyboard.md article---------Co-authored-by: neetcode-gh <77742485+neetcode-gh@users.noreply.github.com>
1 parent3006e86 commit35963c9

12 files changed

+3424
-3
lines changed

‎articles/find-anagram-mappings.md‎

Lines changed: 322 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,322 @@
1+
##1. Brute Force
2+
3+
::tabs-start
4+
5+
```python
6+
classSolution:
7+
defanagramMappings(self,nums1: List[int],nums2: List[int]) -> List[int]:
8+
# List to store the anagram mappings.
9+
mappings= [0]*len(nums1)
10+
11+
for iinrange(len(nums1)):
12+
for jinrange(len(nums2)):
13+
# Store the corresponding index of number in the second list.
14+
if nums1[i]== nums2[j]:
15+
mappings[i]= j
16+
break
17+
18+
return mappings
19+
```
20+
21+
```java
22+
classSolution {
23+
publicint[]anagramMappings(int[]nums1,int[]nums2) {
24+
// List to store the anagram mappings.
25+
int[] mappings=newint[nums1.length];
26+
27+
for (int i=0; i< nums1.length; i++) {
28+
for (int j=0; j< nums2.length; j++) {
29+
// Store the corresponding index of number in the second list.
30+
if (nums1[i]== nums2[j]) {
31+
mappings[i]= j;
32+
break;
33+
}
34+
}
35+
}
36+
return mappings;
37+
}
38+
}
39+
```
40+
41+
```cpp
42+
classSolution {
43+
public:
44+
vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
45+
// List to store the anagram mappings.
46+
vector<int> mappings;
47+
48+
for (int num : nums1) {
49+
for (int i = 0; i < nums2.size(); i++) {
50+
// Store the corresponding index of number in the second list.
51+
if (num == nums2[i]) {
52+
mappings.push_back(i);
53+
break;
54+
}
55+
}
56+
}
57+
return mappings;
58+
}
59+
};
60+
```
61+
62+
```javascript
63+
class Solution {
64+
/**
65+
* @param {number[]} nums1
66+
* @param {number[]} nums2
67+
* @return {number[]}
68+
*/
69+
anagramMappings(nums1, nums2) {
70+
// Array to store the anagram mappings.
71+
const mappings = new Array(nums1.length);
72+
73+
for (let i = 0; i < nums1.length; i++) {
74+
for (let j = 0; j < nums2.length; j++) {
75+
// Store the corresponding index of number in the second array.
76+
if (nums1[i] === nums2[j]) {
77+
mappings[i] = j;
78+
break;
79+
}
80+
}
81+
}
82+
return mappings;
83+
}
84+
}
85+
```
86+
87+
::tabs-end
88+
89+
###Time & Space Complexity
90+
91+
- Time complexity: $O(N^2)$
92+
- Space complexity: $O(1)$ constant space
93+
94+
> Where $N$ is the number of integers in the list `nums1`and `nums2`.
95+
96+
---
97+
98+
##2. HashMap
99+
100+
::tabs-start
101+
102+
```python
103+
classSolution:
104+
def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
105+
# Store the index corresponding to the value in the second list.
106+
valueToPos = {}
107+
for i in range(len(nums2)):
108+
valueToPos[nums2[i]] = i
109+
110+
# List to store the anagram mappings.
111+
mappings = [0] * len(nums1)
112+
for i in range(len(nums1)):
113+
mappings[i] = valueToPos[nums1[i]]
114+
115+
return mappings
116+
```
117+
118+
```java
119+
class Solution {
120+
public int[] anagramMappings(int[] nums1, int[] nums2) {
121+
// Store the index corresponding to the value in the second list.
122+
HashMap<Integer,Integer> valueToPos = new HashMap<>();
123+
for (int i = 0; i < nums2.length; i++) {
124+
valueToPos.put(nums2[i], i);
125+
}
126+
127+
// List to store the anagram mappings.
128+
int[] mappings = new int[nums1.length];
129+
for (int i = 0; i < nums1.length; i++) {
130+
mappings[i] = valueToPos.get(nums1[i]);
131+
}
132+
133+
return mappings;
134+
}
135+
}
136+
```
137+
138+
```cpp
139+
classSolution {
140+
public:
141+
vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
142+
// Store the index corresponding to the value in the second list.
143+
unordered_map<int, int> valueToPos;
144+
for (int i = 0; i < nums2.size(); i++) {
145+
valueToPos[nums2[i]] = i;
146+
}
147+
148+
// List to store the anagram mappings.
149+
vector<int> mappings;
150+
for (int num : nums1) {
151+
mappings.push_back(valueToPos[num]);
152+
}
153+
154+
return mappings;
155+
}
156+
};
157+
```
158+
159+
```javascript
160+
class Solution {
161+
/**
162+
* @param {number[]} nums1
163+
* @param {number[]} nums2
164+
* @return {number[]}
165+
*/
166+
anagramMappings(nums1, nums2) {
167+
// Store the index corresponding to the value in the second list.
168+
const valueToPos = new Map();
169+
for (let i = 0; i < nums2.length; i++) {
170+
valueToPos.set(nums2[i], i);
171+
}
172+
173+
// List to store the anagram mappings.
174+
const mappings = new Array(nums1.length);
175+
for (let i = 0; i < nums1.length; i++) {
176+
mappings[i] = valueToPos.get(nums1[i]);
177+
}
178+
179+
return mappings;
180+
}
181+
}
182+
```
183+
184+
::tabs-end
185+
186+
###Time & Space Complexity
187+
188+
- Time complexity: $O(N)$
189+
- Space complexity: $O(N)$
190+
191+
> Where $N$ is the number of integers in the list `nums1`and `nums2`.
192+
193+
---
194+
195+
##3. Bit Manipulation + Sorting
196+
197+
::tabs-start
198+
199+
```python
200+
classSolution:
201+
def anagramMappings(self, nums1: List[int], nums2: List[int]) -> List[int]:
202+
bitsToShift = 7
203+
numToGetLastBits = (1 << bitsToShift) - 1
204+
205+
# Store the index within the integer itself.
206+
for i in range(len(nums1)):
207+
nums1[i] = (nums1[i] << bitsToShift) + i
208+
nums2[i] = (nums2[i] << bitsToShift) + i
209+
210+
# Sort both lists so that the original integers end up at the same index.
211+
nums1.sort()
212+
nums2.sort()
213+
214+
# List to store the anagram mappings.
215+
mappings =[0] * len(nums1)
216+
217+
for i in range(len(nums1)):
218+
# Store the index in the second list corresponding to the integer index in the first list.
219+
mappings[nums1[i] & numToGetLastBits] = (nums2[i] & numToGetLastBits)
220+
221+
return mappings
222+
```
223+
224+
```java
225+
class Solution {
226+
final int bitsToShift = 7;
227+
final int numToGetLastBits = (1 << bitsToShift) - 1;
228+
229+
public int[] anagramMappings(int[] nums1, int[] nums2) {
230+
// Store the index within the integer itself.
231+
for (int i = 0; i < nums1.length; i++) {
232+
nums1[i] = (nums1[i] << bitsToShift) + i;
233+
nums2[i] = (nums2[i] << bitsToShift) + i;
234+
}
235+
236+
// Sort both lists so that the original integers end up at the same index.
237+
Arrays.sort(nums1);
238+
Arrays.sort(nums2);
239+
240+
// List to store the anagram mappings.
241+
int[] mappings = new int[nums1.length];
242+
for (int i = 0; i < nums1.length; i++) {
243+
// Store the index in the second list corresponding to the integer index in the first list.
244+
mappings[nums1[i] & numToGetLastBits] = (nums2[i] & numToGetLastBits);
245+
}
246+
247+
return mappings;
248+
}
249+
}
250+
```
251+
252+
```cpp
253+
classSolution {
254+
public:
255+
const int bitsToShift = 7;
256+
const int numToGetLastBits = (1 << bitsToShift) - 1;
257+
258+
vector<int> anagramMappings(vector<int>& nums1, vector<int>& nums2) {
259+
// Store the index within the integer itself.
260+
for (int i = 0; i < nums1.size(); i++) {
261+
nums1[i] = (nums1[i] << bitsToShift) + i;
262+
nums2[i] = (nums2[i] << bitsToShift) + i;
263+
}
264+
265+
// Sort both lists so that the original integers end up at the same index.
266+
sort(nums1.begin(), nums1.end());
267+
sort(nums2.begin(), nums2.end());
268+
269+
// List to store the anagram mappings.
270+
vector<int> mappings(nums1.size());
271+
for (int i = 0; i < nums1.size(); i++) {
272+
// Store the index in the second list corresponding to the integer index in the first list.
273+
mappings[nums1[i] & numToGetLastBits] = (nums2[i] & numToGetLastBits);
274+
}
275+
276+
return mappings;
277+
}
278+
};
279+
```
280+
281+
```javascript
282+
classSolution {
283+
/**
284+
*@param{number[]}nums1
285+
*@param{number[]}nums2
286+
*@return{number[]}
287+
*/
288+
anagramMappings(nums1,nums2) {
289+
constbitsToShift=7;
290+
constnumToGetLastBits= (1<< bitsToShift)-1;
291+
292+
// Store the index within the integer itself.
293+
for (let i=0; i<nums1.length; i++) {
294+
nums1[i]= (nums1[i]<< bitsToShift)+ i;
295+
nums2[i]= (nums2[i]<< bitsToShift)+ i;
296+
}
297+
298+
// Sort both arrays so that the original integers end up at the same index.
299+
nums1.sort((a,b)=> a- b);
300+
nums2.sort((a,b)=> a- b);
301+
302+
// Array to store the anagram mappings.
303+
constmappings=newArray(nums1.length);
304+
305+
for (let i=0; i<nums1.length; i++) {
306+
// Store the index in the second array corresponding to the integer index in the first array.
307+
mappings[nums1[i]& numToGetLastBits]= (nums2[i]& numToGetLastBits);
308+
}
309+
310+
return mappings;
311+
}
312+
}
313+
```
314+
315+
::tabs-end
316+
317+
###Time & Space Complexity
318+
319+
- Time complexity: $O(N \log N)$
320+
- Space complexity: $O(\log N)$
321+
322+
> Where $N$ is the number of integers in the list `nums1`and `nums2`.

0 commit comments

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