Dada una string s de longitud N , que contiene dígitos escritos en palabras pero en forma desordenada, la tarea es encontrar los dígitos presentes en la string en forma de palabras y ordenarlos.
Ejemplos:
Entrada: s = “ozerotwneozero”
Salida: 0012
Explicación: La string se puede organizar como “zerozeroonetwo”.
Por lo tanto, los dígitos son 0, 0, 1 y 2.Entrada: s = “otros”
Salida: 123
Enfoque: Este problema se puede resolver usando un mapa basado en la siguiente idea:
Almacene las frecuencias de cada uno de los dígitos y luego intente la representación en palabras de cada uno de los dígitos a partir del 0 al 9.
Siga los siguientes pasos para implementar la idea:
- Tome una variable de string ans = “” y un mapa llamado mp .
- Atraviese string s e inserte todos los caracteres en el mapa.
- Ejecutar bucle para todos los dígitos del 0 al 9
- Ahora verifique en el mapa que todo el carácter de representación alfabética de ese dígito esté presente o no.
- Si encontramos todos los caracteres de cero, agregue ese dígito como char en ans .
- Vuelva a buscar lo mismo hasta que no se encuentre más el mismo dígito.
- Ahora verifique en el mapa que todo el carácter de representación alfabética de ese dígito esté presente o no.
- Regresar respuesta .
A continuación se muestra el código de la implementación anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the digits present
// in a string
string findNumber(string S, int N)
{
// Stores the final ans
string ans = "";
// Stores the corresponding character
// from the word
map<char, int> mp;
for (int i = 0; i < N; i++) {
mp[S[i]]++;
}
while (mp['z'] && mp['e'] && mp['r']
&& mp['o']) {
mp['z']--;
mp['e']--;
mp['r']--;
mp['o']--;
ans += '0';
}
while (mp['o'] && mp['n'] && mp['e']) {
mp['o']--;
mp['n']--;
mp['e']--;
ans += '1';
}
while (mp['t'] && mp['w'] && mp['o']) {
mp['t']--;
mp['w']--;
mp['o']--;
ans += '2';
}
while (mp['t'] && mp['h'] && mp['r']
&& mp['e'] && mp['e']) {
mp['t']--;
mp['h']--;
mp['r']--;
mp['e']--;
mp['e']--;
ans += '3';
}
while (mp['f'] && mp['o'] && mp['u']
&& mp['r']) {
mp['f']--;
mp['o']--;
mp['u']--;
mp['r']--;
ans += '4';
}
while (mp['f'] && mp['i'] && mp['v']
&& mp['e']) {
mp['f']--;
mp['i']--;
mp['v']--;
mp['e']--;
ans += '5';
}
while (mp['s'] && mp['i'] && mp['x']) {
mp['s']--;
mp['i']--;
mp['x']--;
ans += '6';
}
while (mp['s'] && mp['e'] && mp['v']
&& mp['e'] && mp['n']) {
mp['s']--;
mp['e']--;
mp['v']--;
mp['e']--;
mp['n']--;
ans += '7';
}
while (mp['e'] && mp['i'] && mp['g']
&& mp['h'] && mp['t']) {
mp['e']--;
mp['i']--;
mp['g']--;
mp['h']--;
mp['t']--;
ans += '8';
}
while (mp['n'] && mp['i'] && mp['n']
&& mp['e']) {
mp['n']--;
mp['i']--;
mp['n']--;
mp['e']--;
ans += '9';
}
return ans;
}
// Driver program
int main()
{
string s = "zerootwneozero";
int N = s.size();
// Function call
cout << findNumber(s, N);
return 0;
}
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
// Function to find the digits present
// in a string
public static String findNumber(String S, int N)
{
// Stores the final ans
String ans = "";
// Stores the corresponding character
// from the word
TreeMap<Character, Integer> mp
= new TreeMap<Character, Integer>();
for (int i = 0; i < N; i++) {
if (mp.get(S.charAt(i)) != null)
mp.put(S.charAt(i),
mp.get(S.charAt(i)) + 1);
else
mp.put(S.charAt(i), 1);
}
for (char i = 'a'; i < 'z'; i++) {
if (mp.get(i) == null)
mp.put(i, 0);
}
while (mp.get('z') != 0 && mp.get('e') != 0
&& mp.get('r') != 0 && mp.get('o') != 0) {
mp.put('z', mp.get('z') - 1);
mp.put('e', mp.get('e') - 1);
mp.put('r', mp.get('r') - 1);
mp.put('o', mp.get('o') - 1);
ans += '0';
}
while (mp.get('o') != 0 && mp.get('n') != 0
&& mp.get('e') != 0) {
mp.put('o', mp.get('o') - 1);
mp.put('n', mp.get('n') - 1);
mp.put('e', mp.get('e') - 1);
ans += '1';
}
while (mp.get('t') != 0 && mp.get('w') != 0
&& mp.get('o') != 0) {
mp.put('t', mp.get('t') - 1);
mp.put('w', mp.get('w') - 1);
mp.put('o', mp.get('o') - 1);
ans += '2';
}
while (mp.get('t') != 0 && mp.get('h') != 0
&& mp.get('r') != 0 && mp.get('e') != 0
&& mp.get('e') != 0) {
mp.put('t', mp.get('t') - 1);
mp.put('h', mp.get('h') - 1);
mp.put('r', mp.get('r') - 1);
mp.put('e', mp.get('e') - 1);
mp.put('e', mp.get('e') - 1);
ans += '3';
}
while (mp.get('f') != 0 && mp.get('o') != 0
&& mp.get('u') != 0 && mp.get('r') != 0) {
mp.put('f', mp.get('f') - 1);
mp.put('o', mp.get('o') - 1);
mp.put('u', mp.get('u') - 1);
mp.put('r', mp.get('r') - 1);
ans += '4';
}
while (mp.get('f') != 0 && mp.get('i') != 0
&& mp.get('v') != 0 && mp.get('e') != 0) {
mp.put('f', mp.get('f') - 1);
mp.put('i', mp.get('i') - 1);
mp.put('v', mp.get('v') - 1);
mp.put('e', mp.get('e') - 1);
ans += '5';
}
while (mp.get('s') != 0 && mp.get('i') != 0
&& mp.get('x') != 0) {
mp.put('s', mp.get('s') - 1);
mp.put('i', mp.get('i') - 1);
mp.put('x', mp.get('x') - 1);
ans += '6';
}
while (mp.get('s') != 0 && mp.get('e') != 0
&& mp.get('v') != 0 && mp.get('e') != 0
&& mp.get('n') != 0) {
mp.put('s', mp.get('s') - 1);
mp.put('e', mp.get('e') - 1);
mp.put('v', mp.get('v') - 1);
mp.put('e', mp.get('e') - 1);
mp.put('n', mp.get('n') - 1);
ans += '7';
}
while (mp.get('e') != 0 && mp.get('i') != 0
&& mp.get('g') != 0 && mp.get('h') != 0
&& mp.get('t') != 0) {
mp.put('e', mp.get('e') - 1);
mp.put('i', mp.get('i') - 1);
mp.put('g', mp.get('g') - 1);
mp.put('h', mp.get('h') - 1);
mp.put('t', mp.get('t') - 1);
ans += '8';
}
while (mp.get('n') != 0 && mp.get('i') != 0
&& mp.get('n') != 0 && mp.get('e') != 0) {
mp.put('n', mp.get('n') - 1);
mp.put('i', mp.get('i') - 1);
mp.put('n', mp.get('n') - 1);
mp.put('e', mp.get('e') - 1);
ans += '9';
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
String s = "zerootwneozero";
int N = s.length();
// Function call
System.out.print(findNumber(s, N));
}
}
// This code is contributed by Rohit Pradhan
Python3
# Python code to implement the approach
# Function to find the digits present
# in a string
def findNumber(S, N):
# Stores the final ans
ans = ""
# Stores the corresponding character
# from the word
mp = {}
for i in range(N):
if S[i] in mp:
mp[S[i]] += 1
else:
mp[S[i]] = 1
while ('z' in mp and 'e' in mp and 'r' in mp and 'o' in mp and mp['z'] and mp['e'] and mp['r'] and mp['o']):
mp['z'] -= 1
mp['e'] -= 1
mp['r'] -= 1
mp['o'] -= 1
ans += '0'
while ('o' in mp and 'n' in mp and 'e' in mp and mp['o'] and mp['n'] and mp['e']):
mp['o'] -= 1
mp['n'] -= 1
mp['e'] -= 1
ans += '1'
while ('t' in mp and 'w' in mp and 'o' in mp and mp['t'] and mp['w'] and mp['o']):
mp['t'] -= 1
mp['w'] -= 1
mp['o'] -= 1
ans += '2'
while ('t' in mp and 'h' in mp and 'r' in mp and 'e' in mp and 'e' in mp and mp['t'] and mp['h'] and mp['r']
and mp['e'] and mp['e']):
mp['t'] -= 1
mp['h'] -= 1
mp['r'] -= 1
mp['e'] -= 1
mp['e'] -= 1
ans += '3'
while ('f' in mp and 'o' in mp and 'u' in mp and 'r' in mp and mp['f'] and mp['o'] and mp['u']
and mp['r']):
mp['f'] -= 1
mp['o'] -= 1
mp['u'] -= 1
mp['r'] -= 1
ans += '4'
while ('f' in mp and 'i' in mp and 'v' in mp and 'e' in mp and mp['f'] and mp['i'] and mp['v']
and mp['e']):
mp['f'] -= 1
mp['i'] -= 1
mp['v'] -= 1
mp['e'] -= 1
ans += '5'
while ('s' in mp and 'i' in mp and 'x' in mp and mp['s'] and mp['i'] and mp['x']):
mp['s'] -= 1
mp['i'] -= 1
mp['x'] -= 1
ans += '6'
while ('s' in mp and 'e' in mp and 'v' in mp and 'e' in mp and 'n' in mp and mp['s'] and mp['e'] and mp['v']
and mp['e'] and mp['n']):
mp['s'] -= 1
mp['e'] -= 1
mp['v'] -= 1
mp['e'] -= 1
mp['n'] -= 1
ans += '7'
while ('e' in mp and 'i' in mp and 'g' in mp and 'h' in mp and 't' in mp and mp['e'] and mp['i'] and mp['g']
and mp['h'] and mp['t']):
mp['e'] -= 1
mp['i'] -= 1
mp['g'] -= 1
mp['h'] -= 1
mp['t'] -= 1
ans += '8'
while ('n' in mp and 'i' in mp and 'n' in mp and 'e' in mp and mp['n'] and mp['i'] and mp['n']
and mp['e']):
mp['n'] -= 1
mp['i'] -= 1
mp['n'] -= 1
mp['e'] -= 1
ans += '9'
return ans
# Driver program
s = "zerootwneozero"
N = len(s)
# Function call
print(findNumber(s, N))
# this code is contributed by shinjanpatra
C#
// C# code to implement the approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find the digits present
// in a string
static string findNumber(string S, int N)
{
// Stores the final ans
string ans = "";
// Stores the corresponding character
// from the word
IDictionary<char, int> mp = new Dictionary<char, int>();
//Initializing the map
string letters = "abcdefghijklmnopqrstuvwxyz";
for (int i = 0; i < 26; i++) {
if (!mp.ContainsKey(letters[i]))
mp[letters[i]] = 0;
}
//building the map from the given string
for (int i = 0; i < N; i++) {
mp[S[i]]++;
}
//updating the map based on the conditions
//in the question
while (mp['z'] * mp['e'] * mp['r'] * mp['o'] != 0) {
mp['z']--;
mp['e']--;
mp['r']--;
mp['o']--;
ans += '0';
}
while (mp['o'] * mp['n'] * mp['e'] != 0) {
mp['o']--;
mp['n']--;
mp['e']--;
ans += '1';
}
while (mp['t'] * mp['w'] * mp['o'] != 0) {
mp['t']--;
mp['w']--;
mp['o']--;
ans += '2';
}
while (mp['t'] * mp['h'] * mp['r'] * mp['e'] * mp['e'] != 0) {
mp['t']--;
mp['h']--;
mp['r']--;
mp['e']--;
mp['e']--;
ans += '3';
}
while (mp['f'] * mp['o'] * mp['u'] * mp['r'] != 0) {
mp['f']--;
mp['o']--;
mp['u']--;
mp['r']--;
ans += '4';
}
while (mp['f'] * mp['i'] * mp['v'] * mp['e'] != 0) {
mp['f']--;
mp['i']--;
mp['v']--;
mp['e']--;
ans += '5';
}
while (mp['s'] * mp['i'] * mp['x'] != 0) {
mp['s']--;
mp['i']--;
mp['x']--;
ans += '6';
}
while (mp['s'] * mp['e'] * mp['v'] * mp['e'] * mp['n'] != 0) {
mp['s']--;
mp['e']--;
mp['v']--;
mp['e']--;
mp['n']--;
ans += '7';
}
while (mp['e'] * mp['i'] * mp['g'] * mp['h'] * mp['t'] != 0) {
mp['e']--;
mp['i']--;
mp['g']--;
mp['h']--;
mp['t']--;
ans += '8';
}
while (mp['n'] * mp['i'] * mp['n'] * mp['e'] != 0) {
mp['n']--;
mp['i']--;
mp['n']--;
mp['e']--;
ans += '9';
}
return ans;
}
// Driver code
public static void Main(string[] args)
{
string s = "zerootwneozero";
int N = s.Length;
// Function call
Console.WriteLine(findNumber(s, N));
}
}
//This code is contributed by phasing17
Javascript
<script>
// JavaScript code to implement the approach
// Function to find the digits present
// in a string
function findNumber(S, N){
// Stores the final ans
let ans = ""
// Stores the corresponding character
// from the word
let mp = new Map()
for(let i=0;i<N;i++){
if(mp.has(S[i]))
mp.set(S[i], mp.get(S[i])+ 1)
else
mp.set(S[i],1)
}
while (mp.has('z') && mp.has('e') && mp.has('r') && mp.has('o') && mp.get('z')>0 && mp.get('e')>0 && mp.get('r')>0 && mp.get('o')>0){
mp.set('z',mp.get('z')-1);
mp.set('e',mp.get('e')-1);
mp.set('r',mp.get('r')-1);
mp.set('o',mp.get('o')-1);
ans += '0'
}
while (mp.has('o') && mp.has('n') && mp.has('e') && mp.get('o')>0 && mp.get('n')>0 && mp.get('e')>0){
mp.set('o',mp.get('o')-1);
mp.set('n',mp.get('n')-1);
mp.set('e',mp.get('e')-1);
ans += '1'
}
while (mp.has('t') && mp.has('w') && mp.has('o') && mp.get('t')>0 && mp.get('w')>0 && mp.get('o')>0){
mp.set('t',mp.get('t')-1);
mp.set('w',mp.get('w')-1);
mp.set('o',mp.get('o')-1);
ans += '2'
}
while (mp.has('t') && mp.has('h') && mp.has('r') && mp.has('e') && mp.has('e') && mp.get('t')>0 && mp.get('h')>0 && mp.get('r')>0
&& mp.get('e')>0 && mp.get('e')>0){
mp.set('t',mp.get('t')-1);
mp.set('h',mp.get('h')-1);
mp.set('r',mp.get('r')-1);
mp.set('e',mp.get('e')-1);
mp.set('e',mp.get('e')-1);
ans += '3'
}
while (mp.has('f') && mp.has('o') && mp.has('u') && mp.has('r') && mp.get('f')>0 && mp.get('o')>0 && mp.get('u')>0
&& mp.get('r')>0){
mp.set('f',mp.get('f')-1);
mp.set('o',mp.get('o')-1);
mp.set('u',mp.get('u')-1);
mp.set('r',mp.get('r')-1);
ans += '4'
}
while (mp.has('f') && mp.has('i') && mp.has('v') && mp.has('e') && mp.get('f')>0 && mp.get('i')>0 && mp.get('v')>0
&& mp.get('e')>0){
mp.set('f',mp.get('f')-1);
mp.set('i',mp.get('i')-1);
mp.set('v',mp.get('v')-1);
mp.set('e',mp.get('e')-1);
ans += '5'
}
while (mp.has('s') && mp.has('i') && mp.has('x') && mp.get('s')>0 && mp.get('i')>0 && mp.get('x')>0){
mp.set('s',mp.get('s')-1);
mp.set('i',mp.get('i')-1);
mp.set('x',mp.get('x')-1);
ans += '6'
}
while (mp.has('s') && mp.has('e') && mp.has('v') && mp.has('e') && mp.has('n') && mp.get('s')>0 && mp.get('e')>0 && mp.get('v')>0
&& mp.get('e')>0 && mp.get('n')>0){
mp.set('s',mp.get('s')-1)
mp.set('e',mp.get('e')-1)
mp.set('v',mp.get('v')-1)
mp.set('e',mp.get('e')-1)
mp.set('n',mp.get('n')-1)
ans += '7'
}
while (mp.has('e') && mp.has('i') && mp.has('g') && mp.has('h') && mp.has('t') && mp.get('e')>0 && mp.get('i')>0 && mp.get('g')>0
&& mp.get('h')>0 && mp.get('t')>0){
mp.set('e',mp.get('e')-1);
mp.set('i',mp.get('i')-1);
mp.set('g',mp.get('g')-1);
mp.set('h',mp.get('h')-1);
mp.set('t',mp.get('t')-1);
ans += '8'
}
while (mp.has('n') && mp.has('i') && mp.has('n') && mp.has('e') && mp.get('n')>0 && mp.get('i')>0 && mp.get('n')>0
&& mp.get('e')>0){
mp.set('n',mp.get('n')-1);
mp.set('i',mp.get('i')-1);
mp.set('n',mp.get('n')-1);
mp.set('e',mp.get('e')-1);
ans += '9'
}
return ans
}
// Driver program
let s = "zerootwneozero"
let N = s.length
// Function call
document.write(findNumber(s, N))
// this code is contributed by shinjanpatra
</script>
Producción
0012
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aniruddharouth y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA