POPOLNA REVERZIBILNA STRUNA

Dobili ste niz 'str', naloga je preveriti, ali so obrnjeni vsi možni podnizi 'str' prisotni v 'str' ali ne.

Primeri:

niz int

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 str

Recommended Practice Popolna reverzibilna struna Poskusite!

A preprosta rešitev kajti ta težava je ustvariti vse možne podnize 'st' in preveriti, ali njihova obratna stran linearno obstaja v 'str'.
An učinkovita rešitev kajti ta problem temelji na dejstvu, da bo obrat vseh podnizov 'str' obstajal v 'str', če in samo če je celoten niz 'str' palindrom. To dejstvo lahko utemeljimo tako, da upoštevamo, da bo celoten niz obrnjen le, če je palindrom. In če je niz palindrom, potem obstajajo vse nasprotne strani vseh podnizov.

Spodaj je izvedba zgornje ideje.

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# 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>

Izhod

YES

Časovna zahtevnost: O(n) kjer je n dolžina niza.
Pomožni prostor: O(1)

Druga metoda za iskanje niza je popolna reverzibilna ali ne:-

Prav tako lahko preverite, ali je niz popolnoma reverzibilen ali ne, tako da preverite, ali je niz palindromičen ali ne. To dejstvo lahko utemeljimo tako, da upoštevamo, da bo celoten niz obrnjen le, če je palindrom. In če je niz palindrom, potem obstajajo vse nasprotne strani vseh podnizov.

Spodaj je metoda za iskanje palindroma niza:-

primeri programov python

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# 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');

Izhod

YES

Ustvari kviz