Dadas dos strings S y T, la tarea es fusionar estas dos strings agregando un carácter a la vez desde el comienzo de cualquiera de las strings para formar una string resultante . La string resultante debería ser lexicográficamente la string más grande que se puede formar fusionando las strings S y T .
Ejemplos:
Entrada: S = “dbcbb”, T = “cdbbb”
Salida: dcdbcbbbbbEntrada: S = « geeks «, T = « forgeeks»
Salida: gforgeekseeks
Enfoque: la idea más simple para resolver el problema es seleccionar con avidez los primeros caracteres de la string que es lexicográficamente más grande que otros. Por lo tanto, el algoritmo Greedy y la Recursión se pueden usar para resolver el problema. Siga los pasos a continuación para resolver el problema:
- Si alguna de las longitudes de string es 0 , devuelve S + T como respuesta.
- Si S es lexicográficamente más grande que T, devuelve S[0] + largeMerge(S.substr(1), T) .
- De lo contrario, tome el primer carácter de T y llame a la función recursiva más grandeMerge(S, T.substr(1)).
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the approach #include <bits/stdc++.h> using namespace std; // Recursive bfunction for finding // the lexicographically largest string string largestMerge(string s1, string s2) { // If either of the string length is 0, // return the other string if (s1.size() == 0 || s2.size() == 0) return s1 + s2; // If s1 is lexicographically // larger than s2 if (s1 > s2) { // Take first character of s1 // and call the function return s1[0] + largestMerge(s1.substr(1), s2); } // Take first character of s2 // and recursively call function for // remaining string return s2[0] + largestMerge(s1, s2.substr(1)); } // Driver Code int main() { // Given Input string s1 = "geeks"; string s2 = "forgeeks"; // Function Call cout << largestMerge(s1, s2) << endl; return 0; }
Java
// Java program for the approach public class Main { // Recursive bfunction for finding // the lexicographically largest string static String largestMerge(String s1, String s2) { // If either of the string length is 0, // return the other string if (s1.length() == 0 || s2.length() == 0) return s1 + s2; // If s1 is lexicographically // larger than s2 if (s1.compareTo(s2) > 0) { // Take first character of s1 // and call the function return s1.charAt(0) + largestMerge(s1.substring(1), s2); } // Take first character of s2 // and recursively call function for // remaining string return s2.charAt(0) + largestMerge(s1, s2.substring(1)); } public static void main(String[] args) { // Given Input String s1 = "geeks"; String s2 = "forgeeks"; // Function Call System.out.print(largestMerge(s1, s2)); } } // This code is contributed by divyesh072019.
Python3
# Python program for the above approach # Recursive function for finding # the lexicographically largest string def largestMerge(s1, s2): # If either of the string length is 0, # return the other string if len(s1) == 0 or len(s2) == 0: return s1+s2 # If s1 is lexicographically # larger than s2 if(s1 > s2): # Take first character of s1 # and call the function return s1[0]+largestMerge(s1[1:], s2) # Take first character of s2 # and recursively call function for # remaining string return s2[0]+largestMerge(s1, s2[1:]) # Driver code if __name__ == '__main__': # Given Input s1 = "geeks" s2 = "forgeeks" # Function call print(largestMerge(s1, s2)) # This code is contributed by MuskanKalra1
C#
// C# program for the approach using System; class GFG { // Recursive bfunction for finding // the lexicographically largest string static string largestMerge(string s1, string s2) { // If either of the string length is 0, // return the other string if (s1.Length == 0 || s2.Length == 0) return s1 + s2; // If s1 is lexicographically // larger than s2 if (string.Compare(s1, s2) == 1) { // Take first character of s1 // and call the function return s1[0] + largestMerge(s1.Substring(1), s2); } // Take first character of s2 // and recursively call function for // remaining string return s2[0] + largestMerge(s1, s2.Substring(1)); } // Driver Code public static void Main() { // Given Input string s1 = "geeks"; string s2 = "forgeeks"; // Function Call Console.Write(largestMerge(s1, s2)); } } // This code is contributed by ukasp.
Javascript
<script> // JavaScript program for the approach // Recursive bfunction for finding // the lexicographically largest string const largestMerge = (s1, s2) => { // If either of the string length is 0, // return the other string if (s1.length == 0 || s2.length == 0) return s1 + s2; // If s1 is lexicographically // larger than s2 if (s1 > s2) { // Take first character of s1 // and call the function return s1[0] + largestMerge(s1.substr(1), s2); } // Take first character of s2 // and recursively call function for // remaining string return s2[0] + largestMerge(s1, s2.substr(1)); } // Driver Code // Given Input s1 = "geeks"; s2 = "forgeeks"; // Function Call document.write(largestMerge(s1, s2)); // This code is contributed by rakeshsahni </script>
gforgeekseeks
Complejidad temporal: O(M×N), donde M y N son la longitud de la string s1 y s2 respectivamente.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rahulagarwal14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA