Ricerca nel sito web

Numero minimo di operazioni richieste per convertire una stringa in un'altra stringa

Ti vengono fornite due stringhe A e B, il compito è convertire dalla stringa A alla stringa B, se possibile. È consentito eseguire una sola operazione, ovvero inserire qualsiasi carattere da A e inserirlo in primo piano. Controlla se è possibile convertire la stringa. In caso affermativo, viene restituito il numero minimo di operazioni richieste per la trasformazione.

Scenari di input-output

Supponiamo di avere due stringhe A e B con valori rispettivamente "ABD" e "BAD", l'operazione necessaria per convertire la prima stringa in quest'ultima è 1 che sta scambiando i primi due caratteri.

Inserimento

A = "ABD", B = "BAD"

Uscita

1

Considera un altro scenario

Inserimento

A = "EACBD", B = "EABCD"

Uscita

3

Le operazioni devono convertire A in B is

  • Prendi B e metti davanti, EACBD => BEACD

  • Prendi A e metti davanti, BEACD => ABECD

  • Prendi E e metti davanti, ABECD => EABCD

Implementazione di Python

Di seguito è riportata l'implementazione in Python

Esempio

def transformString(A, B):
    if len(A) != len(B):
        return -1    
    count = 0
    i = len(A) - 1
    j = len(B) - 1
    
    while i >= 0 and j >= 0:
        if A[i] == B[j]:
            i -= 1
            j -= 1
        else:
            count += 1
            i -= 1    
    return count
A = "Hello Welcome to Tutorialspoint    "
B = "Tutorialspoint simply easy learning"
print("Operations Required: ", transformString(A, B))  

A = "EACBD"
B = "EABCD"
print("Operations Required: ", transformString(A, B))

Produzione

Operations Required:  35
Operations Required:  3

Approccio

Cerchiamo di comprendere l'approccio seguito dal debug del programma di cui sopra

  • La funzione determina inizialmente se le lunghezze di A e B sono uguali. La funzione restituisce −1 in caso contrario poiché è impossibile trasformare A in B aggiungendo lettere all'inizio.

  • Quando A e B hanno entrambi la stessa lunghezza, la funzione inizializza due puntatori, i e j, che puntano rispettivamente alle estremità di A e B, e una variabile count su 0.

  • Successivamente, la funzione inizia un ciclo while, che continua ad essere eseguito finché i e j sono entrambi non negativi.

  • All'interno del ciclo while, la funzione controlla se il carattere in A[i] è uguale al carattere in B[j]. Se sono uguali, la funzione decrementa sia i che j di 1, saltando di fatto quei caratteri.

  • Se i caratteri non sono uguali, la funzione incrementa count di 1 e decrementa i di 1, "inserendo" di fatto il carattere in A[i] davanti ad A.

  • La funzione determina quindi se j è negativo dopo la terminazione del ciclo while. Se lo è, tutti i caratteri in B sono stati abbinati ai loro equivalenti in A, e il valore di count riflette il minimo indispensabile di inserimenti necessari per cambiare A in B. La funzione restituisce un conteggio.

  • È impossibile cambiare A in B aggiungendo caratteri in primo piano se j non è negativo poiché B contiene ancora caratteri senza corrispondenza. Quando la conversione non è possibile, la funzione restituisce −1.

Implementazione Java

Implementazione Java del codice sopra

Esempio

import java.util.*;

public class Demo{
   public static int transformString(String A, String B) {
   if (A.length() != B.length()) {
      return -1;
   }
   int count = 0;
   int i = A.length() - 1;
   int j = B.length() - 1;

   while (i >= 0 && j >= 0) {
      if (A.charAt(i) == B.charAt(j)) {
         i--;
         j--;
      } else {
         count++;
         i--;
      }
   }
      return count;
   }

   public static void main(String[] args) {
      String A = "Hello Welcome to Tutorialspoint    ";
      String B = "Tutorialspoint simply easy learning";
      int result = transformString(A, B);
      System.out.println("Minimum number of operations required: " + result);

      A = "EACBD";
      B = "EABCD";
      result = transformString(A, B);
      System.out.println("Minimum number of operations required: " + result);
   }
}

Produzione

Minimum number of operations required: 35
Minimum number of operations required: 3

Complessità temporale e spaziale

La funzione di trasformazione ha una complessità temporale O(n), dove n è la lunghezza delle stringhe di input A e B. In questo modo la funzione, che utilizza i due puntatori i e j per eseguire il ciclo i caratteri delle stringhe dalla fine all'inizio, possono confrontare i caratteri e aumentare o diminuire i puntatori e contare a intervalli regolari. La complessità temporale è quindi proporzionale alla lunghezza delle corde.

La funzione di trasformazione ha una complessità spaziale O(1), quindi la quantità di memoria aggiuntiva richiesta è indipendente dalla lunghezza delle stringhe di input. La funzione non genera strutture dati aggiuntive né alloca dinamicamente la memoria; ha solo bisogno di una quantità fissa di memoria per memorizzare le variabili count, i e j.

Articoli correlati: