Compruebe si la concatenación de cualquier permutación de una lista dada de arrays genera la array dada

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros distintos y una lista de piezas de arrays [] de enteros distintos, la tarea es verificar si la lista dada de arrays se puede concatenar en cualquier orden para obtener la array dada. Si es posible, escriba «Sí» . De lo contrario, escriba “No” .

Ejemplos:

Entrada: arr[] = {1, 2, 4, 3}, piezas[][] = {{1}, {4, 3}, {2}}
Salida: Sí
Explicación:
Reorganizar la lista a {{1} , {2}, {4, 3}}.
Ahora, concatenar todas las arrays de la lista genera la secuencia {1, 2, 4, 3} que es igual a la array dada.

Entrada: arr[] = {1, 2, 4, 3}, piezas = {{1}, {2}, {3, 4}}
Salida: No
Explicación:
No hay una permutación posible de una lista dada tal que después de concatenar la secuencia generada se vuelve igual a la array dada.

Enfoque ingenuo: el enfoque más simple es recorrer la array dada arr[] y para cada elemento, arr[i] , verificar si existe alguna array presente en la lista que comience desde arr[i] o no. Si se encuentra que es cierto, entonces incremente i mientras que los elementos presentes en la array son iguales a arr[i] . Si no son iguales, imprima No. Repita los pasos anteriores hasta que i < N . Después de recorrer los elementos de la array dada, imprima Sí .

Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)

Enfoque eficiente: la idea es utilizar el concepto de hash almacenando los índices de los elementos presentes en la array dada arr[] utilizando la estructura de datos del mapa . Siga los pasos a continuación para resolver el problema:

  1. Createa Map para almacenar los índices de los elementos de la array dada arr[] .
  2. Itere sobre cada una de las arrays presentes en la lista y para cada array, siga los pasos a continuación:
    • Encuentre el índice de su primer elemento en la array arr[] del Map .
    • Compruebe si la array obtenida es un subarreglo de la array arr[] o no comienza desde el índice encontrado antes.
  3. Si el subarreglo no es igual al arreglo encontrado, imprima No.
  4. De lo contrario, después de atravesar la array dada , imprima Sí .

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
// to obtain array by concatenating
// the arrays in list pieces[]
bool check(vector<int>& arr,
    vector<vector<int>>& pieces)
{
     
    // Stores the index of element in
    // the given array arr[]
    unordered_map<int, int> m;
 
    for(int i = 0; i < arr.size(); i++)
        m[arr[i]] = i + 1;
 
    // Traverse over the list pieces
    for(int i = 0; i < pieces.size(); i++)
    {
         
        // If item size is 1 and
        // exists in map
        if (pieces[i].size() == 1 &&
          m[pieces[i][0]] != 0)
        {
            continue;
        }
 
        // If item contains > 1 element
        // then check order of element
        else if (pieces[i].size() > 1 &&
               m[pieces[i][0]] != 0)
        {
            int idx = m[pieces[i][0]] - 1;
 
            idx++;
 
            // If end of the array
            if (idx >= arr.size())
                return false;
 
            // Check the order of elements
            for(int j = 1; j < pieces[i].size(); j++)
            {
                 
                // If order is same as
                // the array elements
                if (arr[idx] == pieces[i][j])
                {
                     
                    // Increment idx
                    idx++;
 
                    // If order breaks
                    if (idx >= arr.size() &&
                     j < pieces[i].size() - 1)
                        return false;
                }
 
                // Otherwise
                else
                {
                    return false;
                }
            }
        }
 
        // Return false if the first
        // element doesn't exist in m
        else
        {
            return false;
        }
    }
 
    // Return true
    return true;
}
 
// Driver Code
int main()
{
     
    // Given target list
    vector<int> arr = { 1, 2, 4, 3 };
 
    // Given array of list
    vector<vector<int> > pieces{ { 1 }, { 4, 3 }, { 2 } };
 
    // Function call
    if (check(arr, pieces))
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
    return 0;
}
 
// This code is contributed by akhilsaini

Java

// Java program for the above approach
 
import java.util.*;
 
class GFG {
 
    // Function to check if it is possible
    // to obtain array by concatenating
    // the arrays in list pieces[]
    static boolean check(
        List<Integer> arr,
        ArrayList<List<Integer> > pieces)
    {
        // Stores the index of element in
        // the given array arr[]
        Map<Integer, Integer> m
            = new HashMap<>();
 
        for (int i = 0; i < arr.size(); i++)
            m.put(arr.get(i), i);
 
        // Traverse over the list pieces
        for (int i = 0;
             i < pieces.size(); i++) {
 
            // If item size is 1 and
            // exists in map
            if (pieces.get(i).size() == 1
                && m.containsKey(
                       pieces.get(i).get(0))) {
                continue;
            }
 
            // If item contains > 1 element
            // then check order of element
            else if (pieces.get(i).size() > 1
                     && m.containsKey(
                            pieces.get(i).get(0))) {
 
                int idx = m.get(
                    pieces.get(i).get(0));
 
                idx++;
 
                // If end of the array
                if (idx >= arr.size())
                    return false;
 
                // Check the order of elements
                for (int j = 1;
                     j < pieces.get(i).size();
                     j++) {
 
                    // If order is same as
                    // the array elements
                    if (arr.get(idx).equals(
                            pieces.get(i).get(j))) {
 
                        // Increment idx
                        idx++;
 
                        // If order breaks
                        if (idx >= arr.size()
                            && j < pieces.get(i).size() - 1)
                            return false;
                    }
 
                    // Otherwise
                    else {
                        return false;
                    }
                }
            }
 
            // Return false if the first
            // element doesn't exist in m
            else {
                return false;
            }
        }
 
        // Return true
        return true;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Given target list
        List<Integer> arr
            = Arrays.asList(1, 2, 4, 3);
 
        ArrayList<List<Integer> > pieces
            = new ArrayList<>();
 
        // Given array of list
        pieces.add(Arrays.asList(1));
        pieces.add(Arrays.asList(4, 3));
        pieces.add(Arrays.asList(2));
 
        // Function Call
        if (check(arr, pieces)) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }
    }
}

Python3

# Python3 program for the above approach
from array import *
 
# Function to check if it is possible
# to obtain array by concatenating
# the arrays in list pieces[]
def check(arr, pieces):
     
    # Stores the index of element in
    # the given array arr[]
    m = {}
     
    for i in range(0, len(arr)):
        m[arr[i]] = i + 1
     
    # Traverse over the list pieces
    for i in range(0, len(pieces)):
         
        # If item size is 1 and
        # exists in map
        if (len(pieces[i]) == 1 and
              m[pieces[i][0]] != 0):
            continue
     
        # If item contains > 1 element
        # then check order of element
        elif (len(pieces[i]) > 1 and
                m[pieces[i][0]] != 0):
            idx = m[pieces[i][0]] - 1
            idx = idx+1
             
            # If end of the array
            if idx >= len(arr):
                return False
             
            # Check the order of elements
            for j in range(1, len(pieces[i])):
                 
                # If order is same as
                # the array elements
                if arr[idx] == pieces[i][j]:
                    # Increment idx
                    idx = idx+1
                     
                    # If order breaks
                    if (idx >= len(arr) and
                           j < len(pieces[i]) - 1):
                        return False
                 
                # Otherwise
                else:
                    return False
         
        # Return false if the first
        # element doesn't exist in m
        else:
            return False
     
    # Return true
    return True
 
# Driver Code
if __name__ == "__main__":
     
    arr = [ 1, 2, 4, 3 ]
     
    # Given array of list
    pieces = [ [ 1 ], [ 4, 3 ], [ 2 ] ]
     
    # Function call
    if check(arr, pieces) == True:
        print("Yes")
    else:
        print("No")
 
# This code is contributed by akhilsaini

C#

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
class GFG{
 
// Function to check if it is possible
// to obtain array by concatenating
// the arrays in list pieces[]
static bool check(List<int> arr,
                  List<List<int>> pieces)
{
     
    // Stores the index of element in
    // the given array arr[]
    Dictionary<int,
               int> m = new Dictionary<int,
                                       int>();
 
    for(int i = 0; i < arr.Count; i++)
        m.Add(arr[i], i);
 
    // Traverse over the list pieces
    for(int i = 0; i < pieces.Count; i++)
    {
         
        // If item size is 1 and
        // exists in map
        if (pieces[i].Count == 1 &&
            m.ContainsKey(pieces[i][0]))
        {
            continue;
        }
 
        // If item contains > 1 element
        // then check order of element
        else if (pieces[i].Count > 1 &&
                 m.ContainsKey(pieces[i][0]))
        {
            int idx = m[pieces[i][0]];
 
            idx++;
 
            // If end of the array
            if (idx >= arr.Count)
                return false;
 
            // Check the order of elements
            for(int j = 1; j < pieces[i].Count; j++)
            {
                 
                // If order is same as
                // the array elements
                if (arr[idx] == pieces[i][j])
                {
                     
                    // Increment idx
                    idx++;
 
                    // If order breaks
                    if (idx >= arr.Count &&
                     j < pieces[i].Count - 1)
                        return false;
                }
 
                // Otherwise
                else
                {
                    return false;
                }
            }
        }
         
        // Return false if the first
        // element doesn't exist in m
        else
        {
            return false;
        }
    }
     
    // Return true
    return true;
}
 
// Driver Code
static public void Main()
{
     
    // Given target list
    List<int> arr = new List<int>(){ 1, 2, 4, 3 };
 
    List<List<int> > pieces = new List<List<int> >();
 
    // Given array of list
    pieces.Add(new List<int>(){ 1 });
    pieces.Add(new List<int>(){ 4, 3 });
    pieces.Add(new List<int>(){ 2 });
 
    // Function call
    if (check(arr, pieces))
    {
        Console.WriteLine("Yes");
    }
    else
    {
        Console.WriteLine("No");
    }
}
}
 
// This code is contributed by akhilsaini

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to check if it is possible
// to obtain array by concatenating
// the arrays in list pieces[]
function check(arr, pieces)
{
     
    // Stores the index of element in
    // the given array arr[]
    var m = new Map();
 
    for(var i = 0; i < arr.length; i++)
        m.set(arr[i], i+1)
 
    // Traverse over the list pieces
    for(var i = 0; i < pieces.length; i++)
    {
         
        // If item size is 1 and
        // exists in map
        if (pieces[i].length == 1 &&
          m.get(pieces[i][0]) != 0)
        {
            continue;
        }
 
        // If item contains > 1 element
        // then check order of element
        else if (pieces[i].length > 1 &&
               m.get(pieces[i][0]) != 0)
        {
            var idx = m.get(pieces[i][0]) - 1;
 
            idx++;
 
            // If end of the array
            if (idx >= arr.length)
                return false;
 
            // Check the order of elements
            for(var j = 1; j < pieces[i].length; j++)
            {
                 
                // If order is same as
                // the array elements
                if (arr[idx] == pieces[i][j])
                {
                     
                    // Increment idx
                    idx++;
 
                    // If order breaks
                    if (idx >= arr.length &&
                     j < pieces[i].length - 1)
                        return false;
                }
 
                // Otherwise
                else
                {
                    return false;
                }
            }
        }
 
        // Return false if the first
        // element doesn't exist in m
        else
        {
            return false;
        }
    }
 
    // Return true
    return true;
}
 
// Driver Code
// Given target list
var arr = [ 1, 2, 4, 3 ];
 
// Given array of list
var pieces = [ [ 1 ], [ 4, 3 ], [ 2 ] ];
 
// Function call
if (check(arr, pieces))
{
    document.write( "Yes");
}
else
{
    document.write( "No");
}
 
// This code is contributed by itsok.
</script>
Producción: 

Yes

 

Complejidad de tiempo: O(N*log N) donde N es la longitud de la array dada.
Espacio Auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por offbeat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *