Reemplace las strings dadas a partir de índices dados

Ejemplos:

Entrada:  S = “gforks”, Q = 2, índice[] = {0, 4}, fuentes[] = {“g”, “ks”}, objetivos[] = {“geeks”, “geeks”}
Salida :  geeksforgeeks
Explicación: “g” comienza en el índice 0, por lo que se reemplaza por “geeks”. 
De manera similar, «ks» comienza en el índice 4 y se reemplaza por «geeks».

Entrada:  S = “gforks”, Q = 2, índice[] = {0, 3}, fuentes[] = {“g”, “ss”}, objetivos[] = {“geeks”, “geeks”}
Salida :  geeksforks
Explicación: “g” comienza en el índice 0, por lo que se reemplaza por “geeks”. 
«ss» no comienza en el índice 3 en la S original, por lo que no se reemplaza.

Planteamiento: El problema se puede resolver a partir de la siguiente idea:

Cree una string adicional y para cada operación verifique si es posible reemplazarla. Si es posible, haga los cambios.

Siga los pasos mencionados a continuación para implementar la idea:

• Cree una string vacía ans para almacenar la respuesta final.
• Cree una variable para contar las letras adicionales agregadas en la string ans que la string original.
• Ejecute un bucle al número de
  • Para cada i ^-ésimo reemplazo, agregue la substring de la string original a la string de respuesta de modo que la substring aún no sea parte de la string de respuesta y la substring termine en el i ^-ésimo índice de la string original.
  • Sustituya el origen por el destino si es posible reemplazarlo y actualice los caracteres adicionales agregados.
• Después de completar los reemplazos de Q, agregue la parte restante de la string original tal como está.

A continuación se muestra la implementación del enfoque anterior.

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find and Replace in String
string findAndReplace(string S, int Q, int index[],
                      string sources[], string targets[])
{
    string ans;
    int space = 0;
    for (int i = 0; i < Q; i++) {
 
        // Add the substring from the original string
        // to the answer string
        ans += S.substr(ans.size() - space,
                        index[i] - ans.size() + space);
 
        // Check if given condition satisfies or not
        if (S.substr(index[i], sources[i].size())
            == sources[i]) {
 
            // Substitute the source with the target
            space += targets[i].size() - sources[i].size();
 
            // Add extra space in the space variable
            ans += targets[i];
        }
    }
    ans += S.substr(ans.size() - space);
    return ans;
}
 
// Driver code
int main()
{
    string S;
    S = "gforks";
 
    int Q = 2;
 
    int index[] = { 0, 4 };
    string sources[] = { "g", "ks" };
    string targets[] = { "geeks", "geeks" };
 
    // Function call
    cout << findAndReplace(S, Q, index, sources, targets);
    return 0;
}

// Java Code for the above approach
public class GFG{
 
  // Function to find and Replace in String
  static String findAndReplace(String S, int Q, int[] index,
                               String[] sources, String[] targets)
  {
    String ans="";
    int space = 0;
    for (int i = 0; i < Q; i++) {
 
      // Add the substring from the original string
      // to the answer string
      ans += S.substring(ans.length() - space,index[i]);
 
      // Check if given condition satisfies or not
      if ((S.substring(index[i], index[i] + sources[i].length())).equals(sources[i])) {
 
        // Substitute the source with the target
        space += targets[i].length() - sources[i].length();
 
        // Add extra space in the space variable
        ans += targets[i];
      }
    }
    ans += S.substring(ans.length() - space);
    return ans;
  }
 
 
  public static void main (String []args){
 
    // Code
 
    String S;
    S = "gforks";
 
    int Q = 2;
 
    int[] index = { 0, 4 };
    String[] sources = { "g", "ks" };
    String[] targets = { "geeks", "geeks" };
 
    // Function call
    System.out.println(findAndReplace(S, Q, index, sources, targets));
  }
}
 
// This code is contributed by AnkThon

# python3 code for the above approach
 
# Function to find and Replace in String
def findAndReplace(S, Q, index, sources, targets) :
     
    ans=""
    space = 0
    for i in range(0,Q) :
      # Add the substring from the original string
      # to the answer string
      ans += S[len(ans) - space :  index[i]]
       
      # Check if given condition satisfies or not
      if S[index[i] : index[i] + len(sources[i])] == sources[i] :
        # Substitute the source with the target
        space += len(targets[i]) - len(sources[i])
        # Add extra space in the space variable
        ans += targets[i]
    ans += S[len(ans) - space :]
     
    return ans
 
# Driver code
if __name__ == "__main__" :
     
    S = "gforks"
    Q = 2
    index = [ 0, 4 ]
     
    sources = [ "g", "ks" ]
    targets = [ "geeks", "geeks" ]
   
    # Function call
    print(findAndReplace(S, Q, index, sources, targets))
 
# This code is contributed by adityapatil12

using System;
 
public class GFG{
 
  // Function to find and Replace in String
  static String findAndReplace(String S, int Q, int[] index,
                               String[] sources, String[] targets)
  {
    String ans="";
    int space = 0;
    for (int i = 0; i < Q; i++) {
 
      // Add the substring from the original string
      // to the answer string
      ans += S.Substring(ans.Length - space,
                         index[i] - ans.Length + space);
 
      // Check if given condition satisfies or not
      if (S.Substring(index[i], sources[i].Length)
          == sources[i]) {
 
        // Substitute the source with the target
        space += targets[i].Length - sources[i].Length;
 
        // Add extra space in the space variable
        ans += targets[i];
      }
    }
    ans += S.Substring(ans.Length - space);
    return ans;
  }
 
 
  public static void Main (){
 
    // Code
 
    String S;
    S = "gforks";
 
    int Q = 2;
 
    int[] index = { 0, 4 };
    string[] sources = { "g", "ks" };
    string[] targets = { "geeks", "geeks" };
 
    // Function call
    string ans = findAndReplace(S, Q, index, sources, targets);
    Console.Write(ans);
  }
}
 
// This code is contributed by akashish_.

<script>
    function findAndReplace(S, Q, index,sources,targets)
{
    let ans="";
    let space = 0;
    for (let i = 0; i < Q; i++) {
 
        // Add the substring from the original string
        // to the answer string
        ans += S.substr(ans.length - space,
                        index[i] - ans.length + space);
 
        // Check if given condition satisfies or not
        if (S.substr(index[i], sources[i].length)
            == sources[i]) {
 
            // Substitute the source with the target
            space += targets[i].length - sources[i].length;
 
            // Add extra space in the space variable
            ans += targets[i];
        }
    }
    ans += S.substr(ans.length - space);
    return ans;
}
 
// Driver code
    let S;
    S = "gforks";
 
    let Q = 2;
 
    const index = [ 0, 4 ];
    const sources = [ "g", "ks" ];
    const targets = [ "geeks", "geeks" ];
 
    // Function call
    console.log(findAndReplace(S, Q, index, sources, targets));
     
    // This code is contributed by akashish_.
</script>

geeksforgeeks

Complejidad temporal:  O(|S| * Q)
Espacio auxiliar: O(Q)