Dadas dos strings S y T , la tarea es verificar si algún anagrama de la string S es lexicográficamente más pequeño que cualquier anagrama de la string T.
Ejemplo:
Entrada: S = “xy”, T = “axy”
Salida: Sí
Explicación: Reorganice yx en xy y axy en yxa. Entonces, xy<yxa.Entrada: S = “cd”, T = “abc”
Salida: No
Enfoque: El enfoque consiste en verificar si el anagrama lexicográficamente más pequeño de la string S es más pequeño que el anagrama lexicográficamente más grande de la string T. Si es así, entonces la respuesta es Sí . De lo contrario, no . Ahora, siga los pasos a continuación para resolver esta pregunta:
- Ordene la string S para obtener su anagrama lexicográficamente más pequeño.
- Ordene a la inversa la string T para obtener su anagrama lexicográficamente más grande.
- Compruebe si la nueva string T es mayor que la nueva string S o no. Si es así, imprima Sí . De lo contrario , imprima No.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if any anagram // of string S is lexicographically // smaller than any anagram of string T void CompareAnagrams(string S, string T) { // Sort string S sort(S.begin(), S.end()); // Reverse sort string T sort(T.begin(), T.end(), greater<char>()); // Comparing both the strings if (S.compare(T) < 0) { cout << "Yes" << endl; } else { cout << "No" << endl; } } // Driver code int main() { string S = "cd"; string T = "abc"; CompareAnagrams(S, T); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG { // function to Reverse String static String ReverseString(String myStr) { String nstr = ""; char ch; for (int i = 0; i < myStr.length(); i++) { ch = myStr.charAt(i); // extracts each character nstr = ch + nstr; // adds each character in // front of the existing string } return nstr; } // function to print string in sorted order static String sortString(String str) { char[] arr = str.toCharArray(); Arrays.sort(arr); return new String(arr); } // Function to check if any anagram // of string S is lexicographically // smaller than any anagram of string T static void CompareAnagrams(String S, String T) { // Sort string S sortString(S); // Reverse sort string T T = sortString(T); T = ReverseString(T); // Comparing both the strings if (S.compareTo(T) < 0) { System.out.println("Yes"); } else { System.out.println("No"); } } // Driver Code public static void main(String[] args) { String S = "cd"; String T = "abc"; CompareAnagrams(S, T); } } // This code is contributed by Potta Lokesh
Python3
# Python 3 program for the above approach # Function to check if any anagram # of string S is lexicographically # smaller than any anagram of string T def CompareAnagrams(S, T): # Sort string S S = list(S) S.sort() S = ''.join(S) # Reverse sort string T T = list(T) T.sort(reverse=True) T = ''.join(T) # Comparing both the strings if (S < T): print("Yes") else: print("No") # Driver code if __name__ == "__main__": S = "cd" T = "abc" CompareAnagrams(S, T) # This code is contributed by ukasp.
C#
// C# program for the above approach using System; public class GFG { // function to Reverse String static string ReverseString(string myStr) { char[] myArr = myStr.ToCharArray(); Array.Reverse(myArr); return new string(myArr); } // function to print string in sorted order static void sortString(String str) { char []arr = str.ToCharArray(); Array.Sort(arr); String.Join("",arr); } // Function to check if any anagram // of string S is lexicographically // smaller than any anagram of string T static void CompareAnagrams(string S, string T) { // Sort string S sortString(S); // Reverse sort string T sortString(T); ReverseString(T); // Comparing both the strings if (string.Compare(S, T) < 0) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } // Driver Code public static void Main(String []args) { string S = "cd"; string T = "abc"; CompareAnagrams(S, T); } } // This code is contributed by target_2.
Javascript
<script> // JavaScript Program to implement // the above approach // function to Reverse String function ReverseString(myStr) { let nstr = ""; let ch; for (let i = 0; i < myStr.length; i++) { ch = myStr[i]; // extracts each character nstr = ch + nstr; // adds each character in // front of the existing string } return nstr; } // function to print string in sorted order function sortString(str) { let arr = str.split(); arr.sort(); return arr.join(); } // Function to check if any anagram // of string S is lexicographically // smaller than any anagram of string T function CompareAnagrams(S, T) { // Sort string S sortString(S); // Reverse sort string T T = sortString(T); T = ReverseString(T); // Comparing both the strings if (S.localeCompare(T) < 0) { document.write("Yes"); } else { document.write("No"); } } // Driver code let S = "cd"; let T = "abc"; CompareAnagrams(S, T); // This code is contributed by sanjoy_62. </script>
No
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por 18bhupenderyadav18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA