Movimientos mínimos para formar una string agregando caracteres o agregando la propia string

Dada una string S, necesitamos escribir un programa para verificar si es posible construir la string S dada realizando cualquiera de las siguientes operaciones cualquier cantidad de veces. En cada paso, podemos:

  • Agregue cualquier carácter al final de la string.
  • o agregue la string a la propia string.

Los pasos anteriores se pueden aplicar cualquier número de veces. Necesitamos escribir un programa para imprimir los pasos mínimos requeridos para formar la string.

Ejemplos:

Input : aaaaaaaa
Output : 4 
Explanation: move 1: add 'a' to form "a"
move 2: add 'a' to form "aa"
move 3: append "aa" to form "aaaa" 
move 4: append "aaaa" to form "aaaaaaaa" 

Input: aaaaaa
Output: 4 
Explanation: move 1: add 'a' to form "a"
move 2: add 'a' to form "aa"
move 3: add 'a' to form "aaa" 
move 4: append "aaa" to form "aaaaaa" 

Input: abcabca
Output: 5  

La idea para resolver este problema es usar Programación Dinámica para contar el número mínimo de movimientos. Cree una array denominada dp de tamaño n, donde n es la longitud de la string de entrada. dp[i] almacena el número mínimo de movimientos que se requieren para hacer una substring (0…i). De acuerdo con la pregunta, hay dos movimientos que son posibles:

  1. dp[i] = min(dp[i], dp[i-1] + 1) que significa adición de caracteres.
  2. dp[i*2+1] = min(dp[i]+1, dp[i*2+1]) , la adición de la string se realiza si s[0…i]==s[i+1..i *2+1]
  3. La respuesta se almacenará en dp[n-1] ya que necesitamos formar la string (0..n-1) en el índice.

    A continuación se muestra la implementación de la idea anterior:

    C++

    // CPP program to print the
    // Minimal moves to form a string
    // by appending string and adding characters
    #include <bits/stdc++.h>
    using namespace std;
      
    // function to return the minimal number of moves
    int minimalSteps(string s, int n)
    {
      
        int dp[n];
      
        // initializing dp[i] to INT_MAX
        for (int i = 0; i < n; i++)
            dp[i] = INT_MAX;
      
        // initialize both strings to null
        string s1 = "", s2 = "";
          
        // base case
        dp[0] = 1;
      
        s1 += s[0];
      
        for (int i = 1; i < n; i++) {
            s1 += s[i];
      
            // check if it can be appended
            s2 = s.substr(i + 1, i + 1);
      
            // addition of character takes one step
            dp[i] = min(dp[i], dp[i - 1] + 1);
      
            // appending takes 1 step, and we directly
            // reach index i*2+1 after appending
            // so the number of steps is stord in i*2+1
            if (s1 == s2)
                dp[i * 2 + 1] = min(dp[i] + 1, dp[i * 2 + 1]);
        }
      
        return dp[n - 1];
    }
      
    // Driver Code
    int main()
    {
      
        string s = "aaaaaaaa";
        int n = s.length();
      
        // function call to return minimal number of moves
        cout << minimalSteps(s, n);
      
        return 0;
    }

    Java

    // Java program to print the
    // Minimal moves to form a string
    // by appending string and adding characters
    import java.util.*;
      
    class GFG
    {
      
    // function to return the minimal number of moves
    static int minimalSteps(String s, int n)
    {
      
        int []dp = new int[n];
          
        // initializing dp[i] to INT_MAX
        for (int i = 0; i < n; i++)
            dp[i] = Integer.MAX_VALUE;
      
        // initialize both strings to null
        String s1 = "", s2 = "";
          
        // base case
        dp[0] = 1;
      
        s1 += s.charAt(0);
      
        for (int i = 1; i < n; i++)
        {
            s1 += s.charAt(i);
      
            // check if it can be appended
            s2 = s.substring(i + 1, i + 1);
      
            // addition of character takes one step
            dp[i] = Math.min(dp[i], dp[i - 1] + 1);
      
            // appending takes 1 step, and we directly
            // reach index i*2+1 after appending
            // so the number of steps is stord in i*2+1
            if (s1 == s2)
                dp[i * 2 + 1] = Math.min(dp[i] + 1
                                       dp[i * 2 + 1]);
        }
        return dp[n - 1];
    }
      
    // Driver Code
    public static void main(String args[])
    {
      
        String s = "aaaaaaaa";
        int n = s.length();
      
        // function call to return minimal number of moves
        System.out.println(minimalSteps(s, n)/2);
    }
    }
      
    // This code is contributed by 
    // Shashank_Sharma

    Python3

    # Python program to print the 
    # Minimal moves to form a string 
    # by appending string and adding characters 
      
    INT_MAX = 100000000
      
    # function to return the 
    # minimal number of moves 
    def minimalSteps(s, n):
        dp = [INT_MAX for i in range(n)] 
          
        # initialize both strings to null 
        s1 = ""
        s2 = ""
          
        # base case 
        dp[0] = 1
        s1 += s[0]
          
        for i in range(1, n):
            s1 += s[i]
          
            # check if it can be appended 
            s2 = s[i + 1: i + 1 + i + 1]
          
            # addition of character 
            # takes one step 
            dp[i] = min(dp[i], dp[i - 1] + 1)
          
            # appending takes 1 step, and 
            # we directly reach index i*2+1 
            # after appending so the number
            # of steps is stord in i*2+1 
            if (s1 == s2): 
                dp[i * 2 + 1] = min(dp[i] + 1
                                    dp[i * 2 + 1])
          
        return dp[n - 1]
      
    # Driver Code 
    s = "aaaaaaaa"
    n =len(s)
      
    # function call to return 
    # minimal number of moves 
    print( minimalSteps(s, n) ) 
      
    # This code is contributed 
    # by sahilshelangia

    C#

    // C# program to print the
    // Minimal moves to form a string
    // by appending string and adding characters
    using System;
          
    class GFG
    {
      
    // function to return the minimal number of moves
    static int minimalSteps(String s, int n)
    {
      
        int []dp = new int[n];
          
        // initializing dp[i] to INT_MAX
        for (int i = 0; i < n; i++)
            dp[i] = int.MaxValue;
      
        // initialize both strings to null
        String s1 = "", s2 = "";
          
        // base case
        dp[0] = 1;
      
        s1 += s[0];
      
        for (int i = 1; i < n; i++)
        {
            s1 += s[i];
      
            // check if it can be appended
            s2 = s.Substring(i , 1);
      
            // addition of character takes one step
            dp[i] = Math.Min(dp[i], dp[i - 1] + 1);
      
            // appending takes 1 step, and we directly
            // reach index i*2+1 after appending
            // so the number of steps is stord in i*2+1
            if (s1 == s2)
                dp[i * 2 + 1] = Math.Min(dp[i] + 1, 
                                    dp[i * 2 + 1]);
        }
        return dp[n - 1];
    }
      
    // Driver Code
    public static void Main(String []args)
    {
      
        String s = "aaaaaaaa";
        int n = s.Length;
      
        // function call to return minimal number of moves
        Console.Write(minimalSteps(s, n)/2);
    }
    }
      
    // This code has been contributed by 29AjayKumar

    PHP

    <?php
    // php program to print the
    // Minimal moves to form a 
    // string by appending string
    // and adding characters
      
    // function to return the
    // minimal number of moves
    function minimalSteps($s,$n)
    {
      
        // initializing dp[i] to INT_MAX
        for ($i = 0; $i < $n; $i++)
            $dp[$i] = PHP_INT_MAX;
      
        // initialize both 
        // strings to null
        $s1 = "";
        $s2 = "";
          
        // base case
        $dp[0] = 1;
      
        $s1=$s1.$s[0];
      
        for ($i = 1; $i < $n; $i++) 
        {
            $s1 = $s1.$s[$i];
      
            // check if it can 
            // be appended
            $s2 = substr($s, $i + 1, $i + 1);
      
            // addition of character
            // takes one step
            $dp[$i] = min($dp[$i], 
                      $dp[$i - 1] + 1);
      
            // appending takes 1 step,
            // and we directly
            // reach index i*2+1 
            // after appending
            // so the number of steps 
            // is stord in i*2+1
            if ($s1 == $s2)
                $dp[$i * 2 + 1] = min($dp[$i] + 1,
                                  $dp[$i * 2 + 1]);
        }
      
        return $dp[$n - 1];
    }
      
        // Driver Code
        $s = "aaaaaaaa";
        $n = strlen($s);
      
        // function call to return
        //minimal number of moves
        echo minimalSteps($s, $n);
      
    // This code is contributed by mits 
    ?>

    Producción:

    4
    

    Complejidad de tiempo: O (n 2 ), donde n es la longitud de la string de entrada.

Publicación traducida automáticamente

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