logo

Zkontrolujte, zda lze daný řetězec rozdělit na čtyři různé řetězce

Zkuste to na GfG Practice ' title=

Zadaný řetězec je úkolem zkontrolovat, zda jej můžeme rozdělit na 4 řetězce tak, aby každý řetězec nebyl prázdný a odlišný od druhého.

Příklady:   

Vstup : str[] = 'geeksforgeeks'
Výstup : Ano
'geeks' 'for' 'gee' 'ks' jsou čtyři různé řetězce, které se mohou tvořit z daného řetězce.

Vstup : str[] = 'aaabb'
Výstup : Ne



Pozorujte, zda je délka řetězce větší nebo rovna 10, pak se pokaždé může rozdělit na čtyři části. Předpokládejme, že délka je 10, pak lze vytvořit řetězec délky 1 2 3 4. 
Pro strunu o délce menší než 10 můžeme použít hrubou sílu, tj. iterovat všemi možnými způsoby dělení struny a každý z nich zkontrolovat. 

Li délka je více než 10
vrátit true
Jiný (Pokud je délka menší než 10)
Pomocí metody Brute Force zkontrolujte, zda jej můžeme rozdělit na čtyři různé řetězce.

Níže je implementace výše uvedené myšlenky. 

C++
// C++ program to check if we can break a string // into four distinct strings. #include   using namespace std; // Return if the given string can be split or not. bool check(string s) {  // We can always break a string of size 10 or  // more into four distinct strings.  if (s.size() >= 10)  return true;  // Brute Force  for (int i =1; i < s.size(); i++)  {  for (int j = i + 1; j < s.size(); j++)  {  for (int k = j + 1; k < s.size(); k++)  {  // Making 4 string from the given string  string s1 = s.substr(0 i);  string s2 = s.substr(i j - i);  string s3 = s.substr(j k - j);  string s4 = s.substr(k s.size() - k);  // Checking if they are distinct or not.  if (s1 != s2 && s1 != s3 && s1 != s4 &&  s2 != s3 && s2 != s4 && s3 != s4)  return true;  }  }  }  return false; } // Driven Program int main() {  string str = 'aaabb';  (check(str))? (cout << 'Yes' << endl):  (cout << 'No' << endl);  return 0; } 
Java
// Java program to check if we can break a string  // into four distinct strings.  class GFG {  // Return true if both strings are equal  public static boolean strcheck(String s1 String s2)   {  if (s1 != s2)  return false;  return true;  }  // Return if the given string can be split or not.  public static boolean check(String s)   {  if (s.length() >= 10)  return true;  // Brute Force  for (int i = 1; i < s.length(); i++)   {  for (int j = i + 1; j < s.length(); j++)   {  for (int k = j + 1; k < s.length(); k++)   {    // Making 4 string from the given string  String s1 = '' s2 = '' s3 = '' s4 = '';  try  {  s1 = s.substring(0 i);  s2 = s.substring(i j - i);  s3 = s.substring(j k - j);  s4 = s.substring(k s.length() - k);  }   catch (StringIndexOutOfBoundsException e) {  }  // Checking if they are distinct or not.  if (strcheck(s1 s2) && strcheck(s1 s3) &&   strcheck(s1 s4) && strcheck(s2 s3) &&   strcheck(s2 s4) && strcheck(s3 s4))  return true;  }  }  }  return false;  }  // Driver code  public static void main(String[] args)  {  String str = 'aaabb';  if (check(str))  System.out.println('Yes');  else  System.out.println('No');  } } // This code is contributed by // sanjeev2552 
Python
# Python3 program to check if we can  # break a into four distinct strings.  # Return if the given string can be  # split or not.  def check(s): # We can always break a of size 10 or  # more into four distinct strings.  if (len(s) >= 10): return True # Brute Force  for i in range(1 len(s)): for j in range(i + 1 len(s)): for k in range(j + 1 len(s)): # Making 4 from the given  s1 = s[0:i] s2 = s[i:j - i] s3 = s[j: k - j] s4 = s[k: len(s) - k] # Checking if they are distinct or not.  if (s1 != s2 and s1 != s3 and s1 != s4 and s2 != s3 and s2 != s4 and s3 != s4): return True return False # Driver Code  if __name__ == '__main__': str = 'aaabb' print('Yes') if(check(str)) else print('NO') # This code is contributed # by SHUBHAMSINGH10 
C#
// C# program to check if we can break a string  // into four distinct strings.  using System;   class GFG {  // Return true if both strings are equal  public static Boolean strcheck(String s1  String s2)   {  if (s1.CompareTo(s2) != 0)  return false;  return true;  }  // Return if the given string  // can be split or not.  public static Boolean check(String s)   {  if (s.Length >= 10)  return true;  // Brute Force  for (int i = 1; i < s.Length; i++)   {  for (int j = i + 1; j < s.Length; j++)   {  for (int k = j + 1; k < s.Length; k++)   {    // Making 4 string from the given string  String s1 = '' s2 = ''   s3 = '' s4 = '';  try  {  s1 = s.Substring(0 i);  s2 = s.Substring(i j - i);  s3 = s.Substring(j k - j);  s4 = s.Substring(k s.Length - k);  }   catch (Exception e) {  }  // Checking if they are distinct or not.  if (strcheck(s1 s2) && strcheck(s1 s3) &&   strcheck(s1 s4) && strcheck(s2 s3) &&   strcheck(s2 s4) && strcheck(s3 s4))  return true;  }  }  }  return false;  }  // Driver code  public static void Main(String[] args)  {  String str = 'aaabb';  if (check(str))  Console.WriteLine('Yes');  else  Console.WriteLine('No');  } } // This code is contributed by Princi Singh 
JavaScript
<script>  // JavaScript program to check if we can break a string   // into four distinct strings.     // Return true if both strings are equal  function strcheck(s1 s2)   {  if (s1.localeCompare(s2) != 0)  return false;  return true;  }    // Return if the given string can be split or not.  function check(s)   {  if (s.length >= 10)  return true;    // Brute Force  for (let i = 1; i < s.length; i++)   {  for (let j = i + 1; j < s.length; j++)   {  for (let k = j + 1; k < s.length; k++)   {    // Making 4 string from the given string  let s1 = '' s2 = '' s3 = '' s4 = '';  s1 = s.substring(0 i);  s2 = s.substring(i i + j - i);  s3 = s.substring(j j + k - j);  s4 = s.substring(k k + s.length - k);    // Checking if they are distinct or not.  if (strcheck(s1 s2) && strcheck(s1 s3) &&   strcheck(s1 s4) && strcheck(s2 s3) &&   strcheck(s2 s4) && strcheck(s3 s4))  return true;  }  }  }    return false;  }    let str = 'aaabb';  if (check(str))  document.write('Yes');  else  document.write('No');   </script> 
PHP
 // Return true if the given string can be split into four distinct strings function check($s) { // We can always break a string of size 10 or more into four distinct strings if (strlen($s) >= 10) { return true; } // Brute Force for ($i = 1; $i < strlen($s); $i++) { for ($j = $i + 1; $j < strlen($s); $j++) { for ($k = $j + 1; $k < strlen($s); $k++) { // Making 4 from the given string $s1 = substr($s 0 $i); $s2 = substr($s $i $j - $i); $s3 = substr($s $j $k - $j); $s4 = substr($s $k strlen($s) - $k); // Checking if they are distinct or not if ($s1 != $s2 && $s1 != $s3 && $s1 != $s4 && $s2 != $s3 && $s2 != $s4 && $s3 != $s4) { return true; } } } } return false; } // Driver Code $str = 'aaabb'; echo (check($str) ? 'Yes' : 'NO'); ?> 

Výstup
No

Časová složitost : O(n3
Pomocný prostor: Na)

 

Vytvořit kvíz