完璧なリバーシブルストリング

文字列 'str' が与えられます。タスクは、'str' のすべての可能な部分文字列の反転が 'str' に存在するかどうかを確認することです。

例:

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 完璧なリバーシブルストリング試してみてください!

あ 簡単な解決策 この問題は、「st」の可能なすべての部分文字列を生成し、その逆が「str」に線形に存在するかどうかを確認することです。
アン 効率的なソリューション この問題は、文字列 'str' 全体が回文である場合に限り、'str' のすべての部分文字列の反転が 'str' に存在するという事実に基づいています。この事実は、文字列全体が回文の場合にのみその逆が存在すると考えることで正当化できます。そして、文字列が回文の場合、すべての部分文字列のすべての逆が存在します。

以下は上記のアイデアを実装したものです。

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>

出力

YES

時間計算量: の上） ここで、n は文字列の長さです。
補助スペース: ○(1)

文字列を検索する別の方法は、完全に可逆的かそうでないかです。

文字列が回文であるかどうかをチェックすることで、文字列が完全に可逆であるかどうかを確認することもできます。この事実は、文字列全体が回文の場合にのみその逆が存在すると考えることで正当化できます。そして、文字列が回文の場合、すべての部分文字列のすべての逆が存在します。

以下は文字列の回文を見つける方法です:-

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

出力

YES

クイズの作成