Find Anagram Mappings


  • 0

    Click here to see the full article post


  • 0
    O

    my accepted solution is:
    return [B.index(i) for i in A]
    though sol is accepted , i just wondered if it could be that simple or i am missing on something.


  • 0
    S

    @oorja your solution is correct but is O(n^2) in time complexity (O(1) extra space). Call to index(i) is O(n) and you are doing it for every element in A.


  • 0
    O

    @sergiorp88 yes you are right and thanks


  • 0
    C

    @oorja maybe use unordered_map / HashMap to reduce it to O(1) ?


  • 0
    S

    not sure if the algorithm is correct.
    Please check this input
    int[] A = {12, 28, 28,28};
    int[] B = {28, 28, 12, 28};
    output is {2,3,3,3}

    I think one valid response should be like: {2,0,1,3}

    public int[] anagramMappings_(int[] A, int[] B) {
        HashMap<Integer,List<Integer>> map = new HashMap<>();
        for(int i = 0;i< B.length;i++){
            List<Integer> m =map.getOrDefault(B[i], new ArrayList<>());
            m.add(i);
            map.put(B[i],m);
        }
    
        int[] M = new int[A.length];
        for(int i = 0;i<A.length;i++){
            List<Integer> m = map.get(A[i]);
            if(m != null && m.size() > 0){
                M[i] = m.remove(0);
                if(m.size() == 0 ){
                    map.remove(A[i]);
                }
            }
        }
        return M;
    }

  • 0
    O

    @sergiu.f yes this would be ideal solution to take care of all cases.


  • 0
    J

    According to the Description:

    1. "B is an anagram of A means B is made by randomizing the order of the elements in A. "
    2. "These lists A and B may contain duplicates. If there are multiple answers, output any of them. "

    {2,0,1,3} is just one of the answers while
    int[] A = {12, 28, 28,28};
    int[] B = {28, 28, 12, 28};


  • -1
    O

    class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
    int[] result = new int[A.length];
    for( int i=0; i<A.length;i++){
    for (int j=0;j<B.length;j++){
    if (A[i]==B[j])
    {result[i]=j;
    B[j]=-1;
    break;
    }
    }
    }
    return result;
    }
    }


  • 0

    ,,,
    class Solution {
    public int[] anagramMappings(int[] A, int[] B) {

        int[] P = new int[A.length];
        
        for(int i = 0 ; i < A.length ; i++){
            for( int j = 0 ; j < B.length; j++){
                if(A[i] == B[j]){
                    P[i] = j;   
                }
            }
        }
        
        return P;
    }
    

    }
    ,,,


  • 0
    H
        public int[] AnagramMappings(int[] A, int[] B)
        {
            var C = B.ToList();
            var result = new List<int>();
            A.ToList().ForEach(x => {result.Add(C.FindIndex(item => item == x));});
            return result.ToArray();
        }

  • 0
    A

    var anagramMappings = function(A, B) {
    var result = [];

    for(var i=0;i<A.length;i++){
        result.push(B.indexOf(A[i]));
    }
    
    return result;
    

    };


  • 0
    M

    class Solution {
    public int[] anagramMappings(int[] A, int[] B) {
    List<Integer> ret = new ArrayList<Integer>();
    List<Integer> listB = new ArrayList<Integer>();
    for(int i=0;i<B.length;i++){
    listB.add(B[i]);
    }
    for(int j=0;j<A.length;j++){
    if(listB.indexOf(A[j])>-1){
    ret.add(listB.indexOf(A[j]));
    }
    }

        int[] array = new int[ret.size()]; 
        for(int k=0;k<ret.size();k++){
            array[k] = ret.get(k);
        }
        return array;
    }
    

    }


  • 0
    S

    javascript:

    var anagramMappings = function(A, B) {
        var r = [];
        A.forEach(item => r.push(B.indexOf(item)));
        return r;
    };
    

    python

    class Solution:
        def anagramMappings(self, A, B):
            """
            :type A: List[int]
            :type B: List[int]
            :rtype: List[int]
            """
            r = []
            for v in A:
                r.append(B.index(v))
            return r
    

    ruby:

    def anagram_mappings(a, b)
        a.map {|v| b.find_index(v)}
    end
    

    golang

    func anagramMappings(A []int, B []int) []int {
        result := make([]int,len(A))
        for i,v := range A{
            index := getIndex(B, v)
            result[i] = index
        }
        return result
    }
    
    func getIndex(array []int, element int) (r int){
        for i, v := range array{
            if v == element {
                r = i
                break
            }
        }
        return
    }
    

  • 0
    X

    python: return [B.index(a) for a in A]


  • -1
    M

    I think the space complexity is not O(N) because the space taken by Hashmap should be considered.


  • 0
    D

    With the java code above I ran A = {12, 28, 46, 28} and B = {46, 12, 28, 28} the output was 1,3,0,3
    its stated that These lists A and B may contain duplicates. Should this be considered correct output?


  • 0

    @mayasky.wu said in Find Anagram Mappings:

    I think the space complexity is not O(N) because the space taken by Hashmap should be considered.

    Then what do you think it is?


  • 0
    A

    This solution doesn't handle duplicate entries in the input, consider this input: [1, 1, 2, 3] [2, 3, 1, 1]
    This solution return: [3,3,0,1], which doesn't doesn't map the element at index 2.
    Here's a suggested solution that gives this answer: [2,3,0,1]

    class Solution {
    public:
    vector<int> anagramMappings(vector<int>& A, vector<int>& B)
    {

        vector<int> res(A.size(), 0);
        for(int i = 0; i < A.size(); i++) {res[i] = i;}
        
        for(int i = 0; i < res.size(); i++)
        {
            if(B[res[i]] != A[i])
            {
                for(int j = i+1; i < res.size(); j++)
                {
                    if(B[res[j]] == A[i])
                    {
                        swap(res[i], res[j]);
                        break;
                    }
                }
            }
        }
        
        return res;
    }
    

    };


  • 0
    W

    I was wondering of an extension/generalization of this problem. Here we are asked to find a solution (one solution). What if we are asked, how many solutions are possible? i.e. the count of possible solutions?
    Since elements could repeat, there could certainly be multiple solutions.

    For our extended question, lets say we are allowed to have indices repeated in the solution (I saw that the expected solution in here does have it repeated). So, [3,4,3,2,3] could be a valid solution to a given problem. So, below is the approach that I am taking:-

    Construct a dictionary of all the values in B. Here, key is the value in B and the corresponding dictionary value is the list of indices the value is present in B. Note that this is similar to approach #1 proposed above but here we store all the indices of a value, instead of only one. Lets say there are k different distinct values in B (and of course also in A), we have k keys in our dictionary. Let these distinct keys be m1, m2, ..., mk and the count of indices for each (i.e. the number of times a value is repeating) are p1, p2, ..., pk.
    For e.g. if B = [50,50,32,50,28], then k = 3.
    m1 = 50; p1 = 3, m2 = 32; p2 = 1, m3 = 28; p3 = 1, then, in general, there could be:-
    "p1^p1 * p2^p2 * ... * pk^pk" possible solutions.
    So, for the example above, there are 3^3 * 1^1 * 1^1 = 27 possible solutions.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.