Dado un número entero N , la tarea es contar el número de strings de longitud N que consisten en vocales minúsculas que se pueden generar según las siguientes condiciones:
- Cada ‘a’ sólo puede ir seguida de una ‘e’ .
- Cada ‘e’ solo puede ir seguida de una ‘a’ o una ‘i’.
- Cada ‘i’ no puede ir seguida de otra ‘i’ .
- Cada ‘o’ sólo puede ir seguida de una ‘i’ o una ‘u’ .
- Cada ‘u’ sólo puede ir seguida de una ‘a’ .
Ejemplos:
Entrada: N = 1
Salida: 5
Explicación: Todas las strings que se pueden formar son: “a”, “e”, “i”, “o” y “u”.Entrada: N = 2
Salida: 10
Explicación: Todas las strings que se pueden formar son: “ae”, “ea”, “ei”, “ia”, “ie”, “io”, “iu”, “oi”, “ou” y “ua”.
Enfoque: La idea para resolver este problema es visualizarlo como un problema gráfico . A partir de las reglas dadas se puede construir un gráfico dirigido , donde una arista de u a v significa que v se puede escribir inmediatamente después de u en las strings resultantes. El problema se reduce a encontrar el número de caminos de longitud N en el gráfico dirigido construido. Siga los pasos a continuación para resolver el problema:
- Sean numeradas las vocales a, e, i, o, u como 0, 1, 2, 3, 4 respectivamente, y usando las dependencias que se muestran en el gráfico dado, convierta el gráfico en una relación de lista de adyacencia donde el índice significa la vocal y la lista en ese índice significa un borde de ese índice a los caracteres dados en la lista.
- Inicialice una array 2D dp[N + 1][5] donde dp[N][char] denota el número de caminos dirigidos de longitud N que terminan en un vértice particular char .
- Inicialice dp[i][char] para todos los caracteres como 1 , ya que una string de longitud 1 solo constará de una vocal en la string.
- Para todas las longitudes posibles, digamos i , recorra los bordes dirigidos usando la variable u y realice los siguientes pasos:
- Actualice el valor de dp[i + 1][u] como 0 .
- Atraviese la lista de adyacencia del Node u e incremente el valor de dp[i][u] por dp[i][v] , que almacena la suma de todos los valores de modo que haya un borde dirigido desde el Node u al Node v .
- Después de completar los pasos anteriores, la suma de todos los valores dp[N][i] , donde i pertenece al rango [0, 5) , dará el número total de permutaciones de vocales.
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 find the number of
// vowel permutations possible
int countVowelPermutation(int n)
{
// To avoid the large output value
int MOD = (int)(1e9 + 7);
// Initialize 2D dp array
long dp[n + 1][5];
// Initialize dp[1][i] as 1 since
// string of length 1 will consist
// of only one vowel in the string
for(int i = 0; i < 5; i++)
{
dp[1][i] = 1;
}
// Directed graph using the
// adjacency matrix
vector<vector<int>> relation = {
{ 1 }, { 0, 2 },
{ 0, 1, 3, 4 },
{ 2, 4 }, { 0 }
};
// Iterate over the range [1, N]
for(int i = 1; i < n; i++)
{
// Traverse the directed graph
for(int u = 0; u < 5; u++)
{
dp[i + 1][u] = 0;
// Traversing the list
for(int v : relation[u])
{
// Update dp[i + 1][u]
dp[i + 1][u] += dp[i][v] % MOD;
}
}
}
// Stores total count of permutations
long ans = 0;
for(int i = 0; i < 5; i++)
{
ans = (ans + dp[n][i]) % MOD;
}
// Return count of permutations
return (int)ans;
}
// Driver code
int main()
{
int N = 2;
cout << countVowelPermutation(N);
}
// This code is contributed by Mohit kumar 29
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the number of
// vowel permutations possible
public static int
countVowelPermutation(int n)
{
// To avoid the large output value
int MOD = (int)(1e9 + 7);
// Initialize 2D dp array
long[][] dp = new long[n + 1][5];
// Initialize dp[1][i] as 1 since
// string of length 1 will consist
// of only one vowel in the string
for (int i = 0; i < 5; i++) {
dp[1][i] = 1;
}
// Directed graph using the
// adjacency matrix
int[][] relation = new int[][] {
{ 1 }, { 0, 2 },
{ 0, 1, 3, 4 },
{ 2, 4 }, { 0 }
};
// Iterate over the range [1, N]
for (int i = 1; i < n; i++) {
// Traverse the directed graph
for (int u = 0; u < 5; u++) {
dp[i + 1][u] = 0;
// Traversing the list
for (int v : relation[u]) {
// Update dp[i + 1][u]
dp[i + 1][u] += dp[i][v] % MOD;
}
}
}
// Stores total count of permutations
long ans = 0;
for (int i = 0; i < 5; i++) {
ans = (ans + dp[n][i]) % MOD;
}
// Return count of permutations
return (int)ans;
}
// Driver Code
public static void main(String[] args)
{
int N = 2;
System.out.println(
countVowelPermutation(N));
}
}
Python3
# Python 3 program for the above approach # Function to find the number of # vowel permutations possible def countVowelPermutation(n): # To avoid the large output value MOD = 1e9 + 7 # Initialize 2D dp array dp = [[0 for i in range(5)] for j in range(n + 1)] # Initialize dp[1][i] as 1 since # string of length 1 will consist # of only one vowel in the string for i in range(5): dp[1][i] = 1 # Directed graph using the # adjacency matrix relation = [[1],[0, 2], [0, 1, 3, 4], [2, 4],[0]] # Iterate over the range [1, N] for i in range(1, n, 1): # Traverse the directed graph for u in range(5): dp[i + 1][u] = 0 # Traversing the list for v in relation[u]: # Update dp[i + 1][u] dp[i + 1][u] += dp[i][v] % MOD # Stores total count of permutations ans = 0 for i in range(5): ans = (ans + dp[n][i]) % MOD # Return count of permutations return int(ans) # Driver code if __name__ == '__main__': N = 2 print(countVowelPermutation(N)) # This code is contributed by bgangwar59.
C#
// C# program to find absolute difference
// between the sum of all odd frequenct and
// even frequent elements in an array
using System;
using System.Collections.Generic;
class GFG {
// Function to find the number of
// vowel permutations possible
static int countVowelPermutation(int n)
{
// To avoid the large output value
int MOD = (int)(1e9 + 7);
// Initialize 2D dp array
long[,] dp = new long[n + 1, 5];
// Initialize dp[1][i] as 1 since
// string of length 1 will consist
// of only one vowel in the string
for (int i = 0; i < 5; i++) {
dp[1, i] = 1;
}
// Directed graph using the
// adjacency matrix
List<List<int>> relation = new List<List<int>>();
relation.Add(new List<int> { 1 });
relation.Add(new List<int> { 0, 2 });
relation.Add(new List<int> { 0, 1, 3, 4 });
relation.Add(new List<int> { 2, 4 });
relation.Add(new List<int> { 0 });
// Iterate over the range [1, N]
for (int i = 1; i < n; i++)
{
// Traverse the directed graph
for (int u = 0; u < 5; u++)
{
dp[i + 1, u] = 0;
// Traversing the list
foreach(int v in relation[u])
{
// Update dp[i + 1][u]
dp[i + 1, u] += dp[i, v] % MOD;
}
}
}
// Stores total count of permutations
long ans = 0;
for (int i = 0; i < 5; i++)
{
ans = (ans + dp[n, i]) % MOD;
}
// Return count of permutations
return (int)ans;
}
// Driver code
static void Main() {
int N = 2;
Console.WriteLine(countVowelPermutation(N));
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function to find the number of
// vowel permutations possible
function
countVowelPermutation(n)
{
// To avoid the large output value
let MOD = (1e9 + 7);
// Initialize 2D dp array
let dp = new Array(n + 1);
// Loop to create 2D array using 1D array
for (var i = 0; i < dp.length; i++) {
dp[i] = new Array(2);
}
// Initialize dp[1][i] as 1 since
// string of length 1 will consist
// of only one vowel in the string
for (let i = 0; i < 5; i++) {
dp[1][i] = 1;
}
// Directed graph using the
// adjacency matrix
let relation = [
[ 1 ], [ 0, 2 ],
[ 0, 1, 3, 4 ],
[ 2, 4 ], [ 0 ]
];
// Iterate over the range [1, N]
for (let i = 1; i < n; i++) {
// Traverse the directed graph
for (let u = 0; u < 5; u++) {
dp[i + 1][u] = 0;
// Traversing the list
for (let v in relation[u]) {
// Update dp[i + 1][u]
dp[i + 1][u] += dp[i][v] % MOD;
}
}
}
// Stores total count of permutations
let ans = 0;
for (let i = 0; i < 5; i++) {
ans = (ans + dp[n][i]) % MOD;
}
// Return count of permutations
return ans;
}
// Driver code
let N = 2;
document.write(
countVowelPermutation(N));
</script>
Producción:
10
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohit2sahu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA