Битоническая строка
Для данной строки str задача состоит в том, чтобы проверить, является ли эта строка Bitonic String или нет. Если строка str - это Bitonic String, то выведите «YES», иначе выведите «NO» .
A Bitonic String is a string in which the characters are arranged in increasing order followed by decreasing order of their ASCII values.
Примеры:
Input: str = “abcdfgcba”
Output: YES
Explanation:
In the above string, the ASCII values first increases {a, b, c, d, f, g} and then decreases {g, c, b, a}.
Input: str = “abcdwef”
Output: NO
Подход:
Чтобы решить эту проблему, нам просто нужно пройти по строке и проверить, соответствуют ли значения ASCII символов строки какому-либо из следующих шаблонов:
- Строго возрастает.
- Строго убывает.
- Строго возрастающий, за которым следует строгое уменьшение.
Выполните следующие действия, чтобы решить проблему:
- Начните обход строки и продолжайте проверять, больше ли значение ASCII следующего символа, чем значение ASCII текущего символа.
- Если в какой-то момент значение ASCII следующего символа не превышает значение ASCII текущего символа, прервите цикл.
- Снова начните переход с указанного выше индекса разрыва и проверьте, меньше ли значение ASCII следующего символа, чем значение ASCII текущего символа.
- Если в любой момент значение ASCII следующего символа не меньше, чем значение ASCII текущего символа до достижения конца массива, выведите «NO» и прервите цикл.
- Если конец массива достигнут успешно, выведите «YES» .
Ниже представлена реализация описанного выше подхода:
C ++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if the given // string is bitonic int checkBitonic(string s) { int i, j; // Check for increasing sequence for (i = 1; i < s.size(); i++) { if (s[i] > s[i - 1]) continue ; if (s[i] <= s[i - 1]) break ; } // If end of string has been reached if (i == s.size() - 1) return 1; // Check for decreasing sequence for (j = i + 1; j < s.size(); j++) { if (s[j] < s[j - 1]) continue ; if (s[j] >= s[j - 1]) break ; } i = j; // If the end of string hasn't // been reached if (i != s.size()) return 0; // Return true if bitonic return 1; } // Driver Code int main() { // Given string string s = "abcdfgcba" ; // Function Call (checkBitonic(s) == 1) ? cout << "YES" : cout << "NO" ; return 0; } |
Джава
// Java program for the above approach import java.util.*; class GFG{ // Function to check if the given // String is bitonic static int checkBitonic( char []s) { int i, j; // Check for increasing sequence for (i = 1 ; i < s.length; i++) { if (s[i] > s[i - 1 ]) continue ; if (s[i] <= s[i - 1 ]) break ; } // If end of String has been reached if (i == s.length - 1 ) return 1 ; // Check for decreasing sequence for (j = i + 1 ; j < s.length; j++) { if (s[j] < s[j - 1 ]) continue ; if (s[j] >= s[j - 1 ]) break ; } i = j; // If the end of String hasn't // been reached if (i != s.length) return 0 ; // Return true if bitonic return 1 ; } // Driver Code public static void main(String[] args) { // Given String String s = "abcdfgcba" ; // Function Call System.out.print((checkBitonic( s.toCharArray()) == 1 ) ? "YES" : "NO" ); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program for the above approach # Function to check if the given # string is bitonic def checkBitonic(s): i = 0 j = 0 # Check for increasing sequence for i in range ( 1 , len (s)): if (s[i] > s[i - 1 ]): continue ; if (s[i] < = s[i - 1 ]): break ; # If end of string has been reached if (i = = ( len (s) - 1 )): return True ; # Check for decreasing sequence for j in range (i + 1 , len (s)): if (s[j] < s[j - 1 ]): continue ; if (s[j] > = s[j - 1 ]): break ; i = j; # If the end of string hasn't # been reached if (i ! = len (s) - 1 ): return False ; # Return true if bitonic return True ; # Driver code # Given string s = "abcdfgcba" # Function Call if (checkBitonic(s)): print ( "YES" ) else : print ( "NO" ) # This code is contributed by grand_master |
C #
// C# program for the above approach using System; class GFG{ // Function to check if the given // String is bitonic static int checkBitonic( char []s) { int i, j; // Check for increasing sequence for (i = 1; i < s.Length; i++) { if (s[i] > s[i - 1]) continue ; if (s[i] <= s[i - 1]) break ; } // If end of String has been reached if (i == s.Length - 1) return 1; // Check for decreasing sequence for (j = i + 1; j < s.Length; j++) { if (s[j] < s[j - 1]) continue ; if (s[j] >= s[j - 1]) break ; } i = j; // If the end of String hasn't // been reached if (i != s.Length) return 0; // Return true if bitonic return 1; } // Driver Code public static void Main(String[] args) { // Given String String s = "abcdfgcba" ; // Function call Console.Write((checkBitonic( s.ToCharArray()) == 1) ? "YES" : "NO" ); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program for the above approach // Function to check if the given // string is bitonic function checkBitonic(s) { var i, j; // Check for increasing sequence for (i = 1; i < s.length; i++) { if (s[i] > s[i - 1]) continue ; if (s[i] <= s[i - 1]) break ; } // If end of string has been reached if (i == s.length - 1) return 1; // Check for decreasing sequence for (j = i + 1; j < s.length; j++) { if (s[j] < s[j - 1]) continue ; if (s[j] >= s[j - 1]) break ; } i = j; // If the end of string hasn't // been reached if (i != s.length) return 0; // Return true if bitonic return 1; } // Driver Code // Given string var s = "abcdfgcba" ; // Function Call (checkBitonic(s) == 1) ? document.write( "YES" ) : document.write( "NO" ); // This code is contributed by itsok. </script> |
ДА
Сложность времени: O (N)
Вспомогательное пространство: O (1)
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.