Dados dos enteros N y D , la tarea es encontrar el tamaño de la string más pequeña que contiene todas las permutaciones de longitud N que se pueden formar usando los primeros D dígitos (0, 1, …, D-1) .
Ejemplos:
Entrada: N = 2, D = 2
Salida: 01100
Explicación:
Las permutaciones posibles de longitud 2 a partir de dígitos (0, 1) son {00, 01, 10, 11}.
“01100” es una de esas strings que contiene todas las permutaciones como una substring.
Otras respuestas posibles son “00110”, “10011”, “11001”
Entrada: N = 2, D = 4
Salida: 03322312113020100
Explicación:
aquí todas las posibles permutaciones de longitud 2 de los dígitos {0, 1, 2, 3} son
00 10 20 30
01 11 21 31
02 12 22 32
03 13 23 33
“03322312113020100” es una string de longitud mínima que contiene todas las permutaciones anteriores.
Enfoque:
agregue ‘0’ N-1 veces y llame a DFS en la string en el estado actual. Agregue todos los caracteres D uno por uno. Cada vez después de agregar, verifique si la nueva string se visita o no. Si es así, márquelo como visitado insertándolo en un HashSet y agregue este carácter en la respuesta. Llame recursivamente a la función DFS en los últimos caracteres D. Repita este proceso hasta que todas las substrings posibles de longitud N desde los dígitos D se agreguen a la string. Imprime la string final generada.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the
// minimum length string
// consisting of all
// permutations of length N
// of D digits
#include <bits/stdc++.h>
using namespace std;
// Initialize set to see
// if all the possible
// permutations are present
// in the min length string
set<string> visited;
// To keep min length string
string ans;
// Generate the required string
void dfs(string curr, int D)
{
// Iterate over all the possible
// character
for (int x = 0; x < D; ++x) {
char chr = x + '0';
// Append to make a new string
string neighbour = curr + chr;
// If the new string is not
// visited
if (visited.find(neighbour) == visited.end()) {
// Add in set
visited.insert(neighbour);
// Call the dfs function on
// the last d characters
dfs(neighbour.substr(1), D);
ans.push_back(chr);
}
}
}
string reqString(int N, int D)
{
// Base case
if (N == 1 && D == 1)
return "0";
visited.clear();
ans.clear();
string start;
// Append '0' n-1 times
for (int i = 0; i < N - 1; i++)
start.append("0");
// Call the DFS Function
dfs(start, D);
ans.append(start);
return ans;
}
// Driver Code
int main()
{
int N = 2;
int D = 2;
cout << reqString(N, D) << '\n';
return 0;
}
Java
// Java Program to find the
// minimum length string
// consisting of all
// permutations of length N
// of D digits
import java.io.*;
import java.util.*;
import java.lang.*;
class GeeksforGeeks {
// Initialize hashset to see
// if all the possible
// permutations are present
// in the min length string
static Set<String> visited;
// To keep min length string
static StringBuilder ans;
public static String reqString(int N,
int D)
{
// Base case
if (N == 1 && D == 1)
return "0";
visited = new HashSet<>();
ans = new StringBuilder();
StringBuilder sb = new StringBuilder();
// Append '0' n-1 times
for (int i = 0; i < N - 1; ++i) {
sb.append("0");
}
String start = sb.toString();
// Call the DFS Function
dfs(start, D);
ans.append(start);
return new String(ans);
}
// Generate the required string
public static void dfs(String curr, int D)
{
// Iterate over all the possible
// character
for (int x = 0; x < D; ++x) {
// Append to make a new string
String neighbour = curr + x;
// If the new string is not
// visited
if (!visited.contains(neighbour)) {
// Add in hashset
visited.add(neighbour);
// Call the dfs function on
// the last d characters
dfs(neighbour.substring(1), D);
ans.append(x);
}
}
}
// Driver Code
public static void main(String args[])
{
int N = 2;
int D = 2;
System.out.println(reqString(N, D));
}
}
Python3
# Python3 Program to find the # minimum length string # consisting of all # permutations of length N # of D digits # Initialize set to see # if all the possible # permutations are present # in the min length string visited=set() # To keep min length string ans=[] # Generate the required string def dfs(curr, D): # Iterate over all possible character for c in range(D): c = str(c) # Append to make a new string neighbour = curr + c # If the new string is not visited if neighbour not in visited: # Add in set visited.add(neighbour) # Call the dfs function on the last d characters dfs(neighbour[1:], D) ans.append(c) def reqString(N, D): # Base case if (N == 1 and D == 1): return "0" # Append '0' n-1 times start=''.join(['0']*(N - 1)) # Call the DFS Function dfs(start, D) ans.extend(['0']*(N - 1)) return ''.join(ans) if __name__ == '__main__': N, D = 2, 2 print(reqString(N,D)) # This code is contributed by amartyaghoshgfg.
Javascript
<script>
// JavaScript Program to find the
// minimum length string
// consisting of all
// permutations of length N
// of D digits
// Initialize set to see
// if all the possible
// permutations are present
// in the min length string
let visited = new Set()
// To keep min length string
let ans=[]
// Generate the required string
function dfs(curr, D){
// Iterate over all possible character
for(let c = 0;c<D;c++){
c = parseInt(c)
// Append to make a new string
let neighbour = curr + c
// If the new string is not visited
if(visited.has(neighbour) == false){
// Add in set
visited.add(neighbour)
// Call the dfs function on the last d characters
dfs(neighbour.substring(1), D)
ans.push(c)
}
}
}
function reqString(N, D){
// Base case
if (N == 1 && D == 1)
return "0"
// Append '0' n-1 times
let start=new Array(N - 1).fill('0').join('')
// Call the DFS Function
dfs(start, D)
ans.push(new Array(N - 1).fill('0'))
return ans.join('')
}
// driver code
let N = 2,D = 2
document.write(reqString(N,D))
// This code is contributed by shinjanpatra
</script>
01100
Complejidad de Tiempo: O(N * D N )
Espacio Auxiliar: O(N * D N )
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA