Encuentra dígitos presentes en una string desordenada dada

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.
  • 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

Deja una respuesta

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