## 760. Find Anagram Mappings

Given two lists`A`and`B`, and`B`is an anagram of`A`.`B`is an anagram of`A`means`B`is made by randomizing the order of the elements in`A`.

We want to find anindex mapping`P`, from`A`to`B`. A mapping`P[i] = j`means the`i`th element in`A`appears in`B`at index`j`.

These lists`A`and`B`may contain duplicates. If there are multiple answers, output any of them.

For example, given

``````A = [12, 28, 46, 32, 50]
B = [50, 12, 32, 46, 28]
``````

We should return

``````[1, 4, 3, 2, 0]
``````

as `P[0] = 1`because the`0`th element of`A`appears at`B[1]`, and`P[1] = 4`because the`1`st element of`A`appears at`B[4]`, and so on.

Note:

1. `A, B`have equal lengths in range`[1, 100]`.
2. `A[i], B[i]`are integers in range`[0, 10^5]`.

Thoughts:1

1. (K,V) : (value, list of (index of B))
2. get the value of A[i], retrieve the last element from the mapped list

Code

``````class Solution {
public int[] anagramMappings(int[] A, int[] B) {
int [] result = new int [A.length];
Map<Integer, List<Integer>> map = new HashMap<>();
for( int i = 0; i < B.length; i++){
}

for( int i = 0; i < A.length; i++){
result[i] = map.get(A[i]).remove(map.get(A[i]).size() - 1);
}

return result;
}
}
``````

from diddit's post

Use Sorting:

``````public int[] anagramMappings(int[] A, int[] B) {
int n = A.length;
for(int i = 0; i < n; i++) {
A[i] = (A[i] << 8) + i;
B[i] = (B[i] << 8) + i;
}
Arrays.sort(A);
Arrays.sort(B);
int[] ans = new int[n];
for(int i = 0; i < n; i++)
ans[A[i] & 0xFF] = B[i] & 0xFF;
return ans;
}
``````

from tyuan73's post

``````class Solution {
public:
vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
vector<int> result;
unordered_multimap<int, int> m;
for(int i = 0; i < B.size(); i++){
m.emplace(B[i],i);
}
for(int i: A){
auto iter = m.find(i);
result.push_back(iter->second); // iter->first: value from B; iter->second: associated index in B
// cout<<"iter->first: "<<(iter->first)<<"; iter->second: "<<(iter->second)<<endl;
m.erase(iter);
}

return result;
}
};
``````

from PuckDuck's post

fastest C++:

``````int hashFn(int input) {
return input % 100;
}

class Solution {
public:
vector<int> anagramMappings(vector<int>& A, vector<int>& B) {
unordered_map<int, int> bHash;
vector<int> P;
for (int i = 0; i < B.size(); i++) {
bHash[B[i]] = i;
}
for (int i = 0; i < A.size(); i++) {
P.push_back(bHash[A[i]]);
}

return P;
}
};
``````

fastest Java

``````/*
A = [1,3,2]
B = [1,2,3]
output = [0,2,1]
*/
class Solution {
public int[] anagramMappings(int[] A, int[] B) {
int[] ret = new int[A.length];
for (int i = 0 ; i < ret.length ; i++) {
ret[i] = indexOf(B, A[i]);
}
return ret;
}

private int indexOf(int[] target, int value) {
for (int i = 0 ; i < target.length; i++) {
if (target[i] == value) {
return i;
}
}
return -1;
}
}
``````

fastest Python

``````class Solution(object):
def anagramMappings(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: List[int]
"""
# mapped to the same index of B if duplicates exist
C = {x : i for i, x in enumerate(B)}

return [C[x] for x in A]
``````