Dada una string str , la tarea es verificar si esa string es una string bitónica o no. Si la string str es Bitonic String, imprima «SÍ» , de lo contrario, imprima «NO» .
Una string bitónica es una string en la que los caracteres se organizan en orden creciente seguido de orden decreciente de sus valores ASCII.
Ejemplos:
Entrada: str = “abcdfgcba”
Salida: SÍ
Explicación:
En la string anterior, los valores ASCII primero aumentan {a, b, c, d, f, g} y luego disminuyen {g, c, b, a}.
Entrada: str = “abcdwef”
Salida: NO
Enfoque:
Para resolver el problema, simplemente necesitamos recorrer la string y verificar si los valores ASCII de los caracteres de la string siguen alguno de los siguientes patrones:
- estrictamente creciente.
- estrictamente decreciente.
- Estrictamente creciente seguido de estrictamente decreciente.
Siga estos pasos a continuación para resolver el problema:
- Comience a recorrer la string y siga comprobando si el valor ASCII del siguiente carácter es mayor que el valor ASCII del carácter actual o no.
- Si en algún momento, el valor ASCII del siguiente carácter no es mayor que el valor ASCII del carácter actual, rompa el bucle.
- Nuevamente comience a atravesar desde el índice de interrupción anterior y verifique si el valor ASCII del siguiente carácter es más pequeño que el valor ASCII del carácter actual o no.
- Si en algún momento el valor ASCII del siguiente carácter no es menor que el valor ASCII del carácter actual antes de llegar al final de la array, imprima «NO» y rompa el bucle.
- Si se llega al final de la array con éxito, imprima «SÍ» .
A continuación se muestra la implementación del enfoque anterior:
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
// 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>
YES
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por grand_master y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA