String réversible parfait
Vous recevez une chaîne 'str', la tâche est de vérifier que les inverses de toutes les sous-chaînes possibles de 'str' sont présentes ou non dans 'str'.
Exemples :
Input : str = 'ab' Output: 'NO' // all substrings are 'a''b''ab' but reverse // of 'ab' is not present in str Input : str = 'aba' Output: 'YES' Input : str = 'abab' Output: 'NO' // All substrings are 'a' 'b' 'a' 'b' 'ab' // 'ba' 'ab' 'aba' 'bab' 'abab' but reverse of // 'abab' is not present in strRecommended Practice Corde réversible parfaite Essayez-le !
UN solution simple car ce problème est de générer toutes les sous-chaînes possibles de 'st' et de vérifier si leur inverse existe linéairement dans le 'str'.
Un solution efficace car ce problème est basé sur le fait que l'inverse de toutes les sous-chaînes de « str » existera dans « str » si et seulement si la chaîne entière « str » est un palindrome. Nous pouvons justifier ce fait en considérant que l'ensemble de la chaîne, son inverse n'existera que s'il s'agit d'un palindrome. Et si une chaîne est un palindrome, alors tous les inverses de toutes les sous-chaînes existent.
Vous trouverez ci-dessous la mise en œuvre de l’idée ci-dessus.
C++
// C++ program to check if a string is perfect // reversible or nor #include using namespace std ; // This function basically checks if string is // palindrome or not bool isReversible ( string str ) { int i = 0 j = str . length () -1 ; // iterate from left and right while ( i < j ) { if ( str [ i ] != str [ j ]) return false ; i ++ ; j -- ; } return true ; } // Driver program to run the case int main () { string str = 'aba' ; if ( isReversible ( str )) cout < < 'YES' ; else cout < < 'NO' ; return 0 ; }
Java // Java program to check // if a string is perfect // reversible or nor import java.io.* ; class GFG { // This function basically // checks if string is // palindrome or not static boolean isReversible ( String str ) { int i = 0 j = str . length () - 1 ; // iterate from // left and right while ( i < j ) { if ( str . charAt ( i ) != str . charAt ( j )) return false ; i ++ ; j -- ; } return true ; } // Driver Code public static void main ( String [] args ) { String str = 'aba' ; if ( isReversible ( str )) System . out . print ( 'YES' ); else System . out . print ( 'NO' ); } } // This code is contributed // by anuj_67.
Python3 # Python3 program to check if # a string is perfect reversible or not # This function basically checks # if string is palindrome or not def isReversible ( str ): i = 0 ; j = len ( str ) - 1 ; # iterate from left and right while ( i < j ): if ( str [ i ] != str [ j ]): return False ; i += 1 ; j -= 1 ; return True ; # Driver Code str = 'aba' ; if ( isReversible ( str )): print ( 'YES' ); else : print ( 'NO' ); # This code is contributed by Princi Singh
C# // C# program to check if a string // is perfect reversible or nor using System ; class GFG { // This function basically checks if // string is palindrome or not public static bool isReversible ( string str ) { int i = 0 j = str . Length - 1 ; // iterate from left and right while ( i < j ) { if ( str [ i ] != str [ j ]) { return false ; } i ++ ; j -- ; } return true ; } // Driver Code public static void Main ( string [] args ) { string str = 'aba' ; if ( isReversible ( str )) { Console . Write ( 'YES' ); } else { Console . Write ( 'NO' ); } } } // This code is contributed // by anuj_67
JavaScript < script > // JavaScript program to check if a // string is perfect reversible or not // This function basically checks // if string is palindrome or not function isReversible ( str ) { var i = 0 j = str . length - 1 ; // Iterate from left and right while ( i < j ) { if ( str [ i ] != str [ j ]) return false ; i ++ ; j -- ; } return true ; } // Driver Code var str = 'aba' ; if ( isReversible ( str )) document . write ( 'YES' ); else document . write ( 'NO' ); // This code is contributed by rdtank < /script>
Sortir
YES
Complexité temporelle : Sur) où n est la longueur de la chaîne.
Espace auxiliaire : O(1)
Une autre méthode pour trouver une chaîne est parfaite réversible ou non : -
Vous pouvez également vérifier que la chaîne est parfaitement réversible ou non en vérifiant que la chaîne est palindromique ou non. Nous pouvons justifier ce fait en considérant que l'ensemble de la chaîne, son inverse n'existera que s'il s'agit d'un palindrome. Et si une chaîne est un palindrome, alors tous les inverses de toutes les sous-chaînes existent.
Voici la méthode pour trouver un palindrome d'une chaîne : -
C++ // C++ program to check if a string is perfect // reversible or nor #include using namespace std ; // This function basically checks if string is // palindrome or not bool isReversible ( string s ) { // Stores the reverse of the // string S string p = s ; // Reverse the string P reverse ( p . begin () p . end ()); // If S is equal to P if ( s == p ) { // Return 'Yes' return true ; } // Otherwise return false ; } // Driver program to run the case int main () { string str = 'aba' ; if ( isReversible ( str )) cout < < 'YES' ; else cout < < 'NO' ; return 0 ; } //code by ksam24000
C# //c# code using System ; namespace ConsoleApp1 { class GFG { // Driver program to run the case static void Main ( string [] args ) { string str = 'aba' ; if ( IsReversible ( str )) Console . WriteLine ( 'YES' ); else Console . WriteLine ( 'NO' ); } // This function basically checks if string is // palindrome or not static bool IsReversible ( string s ) { // Stores the reverse of the // string S string p = s ; char [] arr = p . ToCharArray (); // Reverse the string P Array . Reverse ( arr ); p = new string ( arr ); return s == p ; } } } // code by ksam24000
Java // Java program to check if a string is perfect // reversible or not import java.util.* ; public class Main { // This function basically checks if string is // palindrome or not static boolean isReversible ( String s ) { // Stores the reverse of the string s String p = new StringBuilder ( s ). reverse (). toString (); // If s is equal to p if ( s . equals ( p )) { // Return 'Yes' return true ; } // Otherwise return false ; } // Driver program to run the case public static void main ( String [] args ) { String str = 'aba' ; if ( isReversible ( str )) System . out . println ( 'YES' ); else System . out . println ( 'NO' ); } }
Python3 def isReversible ( s ): # Stores the reverse of the string s p = s [:: - 1 ] # If s is equal to p if s == p : # Return True return True # Otherwise return False # Driver program to run the case if __name__ == '__main__' : str = 'aba' if isReversible ( str ): print ( 'YES' ) else : print ( 'NO' ) # This code is contributed by divyansh2212
JavaScript // JavaScript program to check if a string is perfect // reversible or not // This function basically checks if string is // palindrome or not function isReversible ( s ) { // Stores the reverse of the // string S let p = s . split ( '' ). reverse (). join ( '' ); // If S is equal to P if ( s == p ) { // Return 'Yes' return true ; } // Otherwise return false ; } // Driver program to run the case let str = 'aba' ; if ( isReversible ( str )) console . log ( 'YES' ); else console . log ( 'NO' );
Sortir
YES
Créer un quiz
