Generar una secuencia con las operaciones dadas

Dada una string  S  que contiene solo  yo  (aumento) y  D  (disminución). La tarea es devolver cualquier permutación de enteros [0, 1, …, N] donde N ≤ Longitud de S tal que para todo i = 0, …, N-1
 

  1. Si S[i] == “D”, entonces A[i] > A[i+1]
  2. Si S[i] == “I”, entonces A[i] < A[i+1].

Tenga en cuenta que la salida debe contener elementos distintos.
Ejemplos: 
 

Entrada: S = “DDI” 
Salida: [3, 2, 0, 1]
Entrada: S = “IDID” 
Salida: [0, 4, 1, 3, 2] 
 

Enfoque: Si S[0] == “I” , elija  0  como primer elemento. Del mismo modo, si S[0] == “D” , elija  norte  como primer elemento. Ahora, para cada  yo  operación, elija el siguiente elemento máximo que no se haya elegido antes del rango [0, N] , y para la  D  operación, elija el siguiente mínimo.
A continuación se muestra la implementación del enfoque anterior:
 

C++

//C++ Implementation of above approach
#include<bits/stdc++.h>
using namespace std;
    // function to find minimum required permutation
    void  StringMatch(string s)
    {
    int lo=0, hi = s.length(), len=s.length();
    vector<int> ans;
    for (int x=0;x<len;x++)
    {
        if (s[x] == 'I')
        {
            ans.push_back(lo) ;
            lo += 1;
            }
        else
        {
            ans.push_back(hi) ;
            hi -= 1;
            }
    }
            ans.push_back(lo) ;
    cout<<"[";
    for(int i=0;i<ans.size();i++)
    {
    cout<<ans[i];
    if(i!=ans.size()-1)
    cout<<",";
    }
    cout<<"]";
}
// Driver code
int main()
{
string S = "IDID";
StringMatch(S);
return 0;
}
//contributed by Arnab Kundu

Java

// Java Implementation of above approach
import java.util.*;
 
class GFG
{
 
// function to find minimum required permutation
static void StringMatch(String s)
{
    int lo=0, hi = s.length(), len=s.length();
    Vector<Integer> ans = new Vector<>();
    for (int x = 0; x < len; x++)
    {
        if (s.charAt(x) == 'I')
        {
            ans.add(lo) ;
            lo += 1;
        }
        else
        {
            ans.add(hi) ;
            hi -= 1;
        }
    }
            ans.add(lo) ;
    System.out.print("[");
    for(int i = 0; i < ans.size(); i++)
    {
        System.out.print(ans.get(i));
        if(i != ans.size()-1)
            System.out.print(",");
    }
    System.out.print("]");
}
 
// Driver code
public static void main(String[] args)
{
    String S = "IDID";
    StringMatch(S);
}
}
 
// This code is contributed by Rajput-Ji

Python

# Python Implementation of above approach
 
# function to find minimum required permutation
def StringMatch(S):
    lo, hi = 0, len(S)
    ans = []
    for x in S:
        if x == 'I':
            ans.append(lo)
            lo += 1
        else:
            ans.append(hi)
            hi -= 1
 
    return ans + [lo]
 
# Driver code
S = "IDID"
print(StringMatch(S))

C#

// C# Implementation of above approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// function to find minimum required permutation
static void StringMatch(String s)
{
    int lo=0, hi = s.Length, len=s.Length;
    List<int> ans = new List<int>();
    for (int x = 0; x < len; x++)
    {
        if (s[x] == 'I')
        {
            ans.Add(lo) ;
            lo += 1;
        }
        else
        {
            ans.Add(hi) ;
            hi -= 1;
        }
    }
            ans.Add(lo) ;
    Console.Write("[");
    for(int i = 0; i < ans.Count; i++)
    {
        Console.Write(ans[i]);
        if(i != ans.Count-1)
            Console.Write(",");
    }
    Console.Write("]");
}
 
// Driver code
public static void Main(String[] args)
{
    String S = "IDID";
    StringMatch(S);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of above approach
 
// function to find minimum required permutation
    function  StringMatch(s)
    {
    var lo=0, hi = s.length, len=s.length;
    var ans=[];
    for (var x=0;x<len;x++)
    {
        if (s[x] == 'I')
        {
            ans.push(lo) ;
            lo += 1;
            }
        else
        {
            ans.push(hi) ;
            hi -= 1;
            }
    }
            ans.push(lo) ;
    document.write("[");
    for(var i=0;i<ans.length;i++)
    {
     document.write(ans[i]);
    if(i!=ans.length -1)
     document.write(", ");
    }
     document.write("]");
}
 
var S = "IDID";
StringMatch(S);
 
 
// This code is contributed by SoumikMondal
 
</script>
Producción: 

[0, 4, 1, 3, 2]

 

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad 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 *