Encuentre el mínimo común múltiplo (LCM) de strings dadas

Dadas dos strings str1 y str2 de longitudes N y M respectivamente. La tarea es encontrar el mínimo común múltiplo (MCM) de ambas strings y, si no existe, imprimir -1 .

Nota: MCM de dos strings es una string que se puede formar concatenando las strings entre sí y tiene la longitud más corta.

Ejemplos:

Entrada : str1 = “baba”, str2 = “ba”
Salida : baba
Explicación : “baba” es la string más pequeña que se puede obtener tanto de str1 como de str2.
Tenga en cuenta que también se puede formar «babababa», pero la longitud de la cuerda no es lo menos importante.
 

Entrada : str1 = “aba”, str2 = “ab”
Salida : -1
Explicación: No se puede formar tal string.

Enfoque : Este problema es similar a encontrar la string más corta formada al concatenar A x veces y B y veces . La tarea se resuelve haciendo que las longitudes de ambas strings sean iguales y luego verificando si ambas strings se vuelven iguales o no. Siga los pasos a continuación para resolver el problema:

• Iterar hasta que las longitudes de ambas strings sean desiguales.
• Si la longitud de str1 es menor que str2 , agregue str1 a sí mismo o haga lo mismo para str2 .
• Después del ciclo, si ambos son iguales, imprima cualquier string, de lo contrario, imprima -1.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the lcm of both strings
string findLcm(string str1, string str2)
{
    string x = str1, y = str2;
 
    // While their length is unequal
    while (x.length() != y.length()) {
        if (x.length() < y.length())
            x += str1;
        else
            y += str2;
    }
 
    if (x == y)
        return x;
    return "";
}
 
// Driver Code
int main()
{
    string str1 = "ba", str2 = "baba";
 
    string ans = findLcm(str1, str2);
    if (ans != "")
        cout << ans;
    else {
        cout << -1;
    }
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG{
 
  // Function to find the lcm of both Strings
  static String findLcm(String str1, String str2)
  {
    String x = str1, y = str2;
 
    // While their length is unequal
    while (x.length() != y.length()) {
      if (x.length() < y.length())
        x += str1;
      else
        y += str2;
    }
 
    if (x.equals(y))
      return x;
    return "";
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    String str1 = "ba", str2 = "baba";
 
    String ans = findLcm(str1, str2);
    if (ans != "")
      System.out.print(ans);
    else {
      System.out.print(-1);
    }
  }
}
 
// This code is contributed by shikhasingrajput

# Python code for the above approach
 
# Function to find the lcm of both strings
def findLcm(str1, str2):
    x = str1
    y = str2
 
    # While their length is unequal
    while (len(x) != len(y)):
        if (len(x) < len(y)):
            x += str1;
        else:
            y += str2;
 
    if (x == y):
        return x;
    return "";
 
# Driver Code
str1 = "ba"
str2 = "baba"
 
ans = findLcm(str1, str2)
if (ans != ""):
    print(ans);
else:
    print(-1);
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
class GFG
{
  // Function to find the lcm of both strings
  static string findLcm(string str1, string str2)
  {
    string x = str1, y = str2;
 
    // While their length is unequal
    while (x.Length != y.Length) {
      if (x.Length < y.Length)
        x += str1;
      else
        y += str2;
    }
 
    if (x == y)
      return x;
    return "";
  }
 
  // Driver Code
  public static void Main()
  {
    string str1 = "ba", str2 = "baba";
 
    string ans = findLcm(str1, str2);
    if (ans != "")
      Console.Write(ans);
    else {
      Console.Write(-1);
    }
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
      // JavaScript code for the above approach
 
      // Function to find the lcm of both strings
      function findLcm(str1, str2) {
          let x = str1, y = str2;
 
          // While their length is unequal
          while (x.length != y.length) {
              if (x.length < y.length)
                  x += str1;
              else
                  y += str2;
          }
 
          if (x == y)
              return x;
          return "";
      }
 
      // Driver Code
 
      let str1 = "ba", str2 = "baba";
 
      let ans = findLcm(str1, str2);
      if (ans != "")
          document.write(ans);
      else {
          document.write(-1);
      }
 
     // This code is contributed by Potta Lokesh
  </script>

baba

Complejidad de Tiempo : O(N + M)
Espacio Auxiliar : O(N + M)