Dada una string S de longitud N, que consiste en caracteres en minúsculas que contienen representaciones en inglés reordenadas de dígitos [0 – 9], la tarea es imprimir esos dígitos en orden ascendente.
Ejemplos:
Entrada: S = «fviefuro»
Salida: 45
Explicación: La string dada se puede reorganizar a «cuatrocinco». Por lo tanto, los dígitos representados por las strings son 4 y 5.Entrada: S = «owoztneoer»
Salida: 012
Explicación: La string dada se puede reorganizar para obtener «cerouNodes». Por lo tanto, los dígitos representados por las strings son 0, 1 y 2.
Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones de la string dada y, para cada permutación, verificar si es posible encontrar dígitos válidos representados por la string. Si es cierto, imprima el conjunto de dígitos en orden ascendente.
Complejidad temporal: O(N * N!)
Espacio auxiliar: O(1)
Enfoque eficiente: la idea se basa en la observación de que algunos caracteres solo aparecen en un número.
En ‘cero’, el carácter ‘z’ es único.
En ‘dos’, el carácter ‘w’ es único.
En ‘cuatro’, el carácter ‘u’ es único.
En ‘seis’, el carácter ‘x’ es único.
En ‘ocho’, el carácter ‘g’ es único.
En ‘tres’, el carácter ‘h’ es único ya que ya se ha considerado la palabra «ocho» que tiene el carácter ‘h’.
En ‘uno’, el carácter ‘o’ es único ya que las palabras que tienen el carácter ‘o’ ya se han considerado.
En ‘cinco’, el carácter f’ es único ya que ya se ha considerado la palabra «cuatro» que tiene el carácter ‘f’.
En ‘siete’, el carácter ‘v’ es único.
En ‘nueve’, el carácter ‘i’ es único ya que ya se han considerado las palabras que tienen el carácter ‘i’.
Siga los pasos a continuación para resolver el problema:
- Inicialice una string vacía y almacene el resultado requerido.
- Almacene la frecuencia de cada carácter de la string en M .
- Cree una asignación de un carácter único a su string correspondiente .
- Recorra el mapa y realice los siguientes pasos:
- Almacene el carácter único correspondiente al dígito en una variable x .
- Obtenga la ocurrencia de x en M y guárdela en una variable freq .
- Agregue el dígito correspondiente, freq número de veces a ans .
- Recorra la palabra correspondiente a x y disminuya la frecuencia de sus caracteres por freq en M .
- Imprime la string, y como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement the above approach
// Function to construct the original set of digits
// from the string in ascending order
#include <bits/stdc++.h>
using namespace std;
string construct_digits(string s)
{
// Store the unique characters
// corresponding to word and number
vector<char>k = { 'z', 'w', 'u', 'x', 'g',
'h', 'o', 'f', 'v', 'i' };
vector<string>l = { "zero", "two", "four", "six", "eight",
"three", "one", "five", "seven", "nine" };
vector<int>c = { 0, 2, 4, 6, 8, 3, 1, 5, 7, 9 };
// Store the required result
vector<int> ans = {};
// Store the frequency of
// each character of S
unordered_map<char,int>d;
for(int i = 0; i < s.length(); i++)
{
d[s[i]]++;
}
// Traverse the unique characters
for(int i = 0; i < k.size(); i++)
{
// Store the count of k[i] in S
int x = 0;
if (d.find(k[i]) != d.end())
x = d[k[i]];
// Traverse the corresponding word
for(int j = 0; j < l[i].length(); j++)
{
// Decrement the frequency
// of characters by x
if (d.find(l[i][j]) != d.end())
d[l[i][j]]-= x;
}
// Append the digit x times to ans
for(int j = 0; j < x; j++)
ans.push_back(c[i]);
}
// Sort the digits in ascending order
sort(ans.begin(),ans.end());
string res;
for(auto x: ans)res+=(x+'0');
return res;
}
// Driver Code
int main()
{
// Given string, s
string s = "fviefuro";
// Function Call
cout<<(construct_digits(s));
}
// This code is contributed by shinjanpatra
Java
// Java program to implement the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to construct the original set of digits
// from the string in ascending order
static String construct_digits(String s)
{
// Store the unique characters
// corresponding to word and number
char[] k = { 'z', 'w', 'u', 'x', 'g',
'h', 'o', 'f', 'v', 'i' };
String[] l = { "zero", "two", "four", "six", "eight",
"three", "one", "five", "seven", "nine" };
int[] c = { 0, 2, 4, 6, 8, 3, 1, 5, 7, 9 };
// Store the required result
List<Integer> ans = new ArrayList<>();
// Store the frequency of
// each character of S
HashMap<Character, Integer> d = new HashMap<>();
for(int i = 0; i < s.length(); i++)
{
d.put(s.charAt(i),
d.getOrDefault(s.charAt(i), 0) + 1);
}
// Traverse the unique characters
for(int i = 0; i < k.length; i++)
{
// Store the count of k[i] in S
int x = 0;
if (d.containsKey(k[i]))
x = d.get(k[i]);
// Traverse the corresponding word
for(int j = 0; j < l[i].length(); j++)
{
// Decrement the frequency
// of characters by x
if (d.containsKey(l[i].charAt(j)))
d.put(l[i].charAt(j),
d.get(l[i].charAt(j)) - x);
}
// Append the digit x times to ans
for(int j = 0; j < x; j++)
ans.add(c[i]);
}
// Sort the digits in ascending order
Collections.sort(ans);
String str = "";
for(int val : ans)
str += val;
return str;
}
// Driver Code
public static void main(String[] args)
{
// Given string, s
String s = "fviefuro";
// Function Call
System.out.println(construct_digits(s));
}
}
// This code is contributed by Kingash
Python3
# Python program to implement the above approach from collections import Counter # Function to construct the original set of digits # from the string in ascending order def construct_digits(s): # Store the unique characters # corresponding to word and number k = ["z", "w", "u", "x", "g", "h", "o", "f", "v", "i"] l = ["zero", "two", "four", "six", "eight", "three", "one", "five", "seven", "nine"] c = [0, 2, 4, 6, 8, 3, 1, 5, 7, 9] # Store the required result ans = [] # Store the frequency of # each character of S d = Counter(s) # Traverse the unique characters for i in range(len(k)): # Store the count of k[i] in S x = d.get(k[i], 0) # Traverse the corresponding word for j in range(len(l[i])): # Decrement the frequency # of characters by x d[l[i][j]]-= x # Append the digit x times to ans ans.append(str(c[i])*x) # Sort the digits in ascending order ans.sort() return "".join(ans) # Driver Code # Given string, s s = "fviefuro" # Function Call print(construct_digits(s))
C#
// C# program to implement the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to construct the original set of digits
// from the string in ascending order
static string construct_digits(string s)
{
// Store the unique characters
// corresponding to word and number
char[] k = { 'z', 'w', 'u', 'x', 'g',
'h', 'o', 'f', 'v', 'i' };
string[] l = { "zero", "two", "four", "six", "eight",
"three", "one", "five", "seven", "nine" };
int[] c = { 0, 2, 4, 6, 8, 3, 1, 5, 7, 9 };
// Store the required result
List<string> ans = new List<string>();
// Store the frequency of
// each character of S
Dictionary<char,
int> d = new Dictionary<char,
int>();
for(int i = 0; i < s.Length; i++)
{
if (!d.ContainsKey(s[i]))
d[s[i]] = 0;
d[s[i]] += 1;
}
// Traverse the unique characters
for(int i = 0; i < k.Length; i++)
{
// Store the count of k[i] in S
int x = 0;
if (d.ContainsKey(k[i]))
x = d[k[i]];
// Traverse the corresponding word
for(int j = 0; j < l[i].Length; j++)
{
// Decrement the frequency
// of characters by x
if (d.ContainsKey(l[i][j]))
d[l[i][j]] -= x;
}
// Append the digit x times to ans
ans.Add(((c[i]) * x).ToString());
}
// Sort the digits in ascending order
ans.Sort();
string str = (String.Join("", ans.ToArray()));
return str.Replace("0", "");
}
// Driver Code
public static void Main(string[] args)
{
// Given string, s
string s = "fviefuro";
// Function Call
Console.WriteLine(construct_digits(s));
}
}
// This code is contributed by ukasp
Javascript
<script>
// Javascript program to implement the above approach
// Function to construct the original set of digits
// from the string in ascending order
function construct_digits(s)
{
// Store the unique characters
// corresponding to word and number
let k = [ 'z', 'w', 'u', 'x', 'g',
'h', 'o', 'f', 'v', 'i' ];
let l = [ "zero", "two", "four", "six", "eight",
"three", "one", "five", "seven", "nine" ];
let c = [ 0, 2, 4, 6, 8, 3, 1, 5, 7, 9 ];
// Store the required result
let ans = [];
// Store the frequency of
// each character of S
let d = new Map();
for(let i = 0; i < s.length; i++)
{
if(!d.has(s[i]))
d.set(s[i],0);
d.set(s[i],
d.get(s[i]) + 1);
}
// Traverse the unique characters
for(let i = 0; i < k.length; i++)
{
// Store the count of k[i] in S
let x = 0;
if (d.has(k[i]))
x = d.get(k[i]);
// Traverse the corresponding word
for(let j = 0; j < l[i].length; j++)
{
// Decrement the frequency
// of characters by x
if (d.has(l[i][j]))
d.set(l[i][j],
d.get(l[i][j]) - x);
}
// Append the digit x times to ans
for(let j = 0; j < x; j++)
ans.push(c[i]);
}
// Sort the digits in ascending order
ans.sort();
return ans.join("");
}
// Driver Code
// Given string, s
let s = "fviefuro";
// Function Call
document.write(construct_digits(s));
// This code is contributed by avanitrachhadiya2155
</script>
45
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por maheswaripiyush9 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA