Dada una string ‘s’, la tarea es encontrar si los caracteres de la string están en orden alfabético. La string contiene solo caracteres en minúsculas.
Ejemplos:
Input: Str = "aabbbcc" Output: In alphabetical order Input: Str = "aabbbcca" Output: Not in alphabetical order
Un enfoque simple:
- Almacene la string en una array de caracteres y ordene la array.
- Si los caracteres en la array ordenada están en el mismo orden que la string, imprima ‘En orden alfabético’.
- Imprima ‘No en orden alfabético’ de lo contrario.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function that checks whether
// the string is in alphabetical
// order or not
bool isAlphabaticOrder(string s)
{
// length of the string
int n = s.length();
// create a character array
// of the length of the string
char c[n];
// assign the string
// to character array
for (int i = 0; i < n; i++) {
c[i] = s[i];
}
// sort the character array
sort(c, c + n);
// check if the character array
// is equal to the string or not
for (int i = 0; i < n; i++)
if (c[i] != s[i])
return false;
return true;
}
// Driver code
int main()
{
string s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of above approach
// import Arrays class
import java.util.Arrays;
public class GFG {
// Function that checks whether
// the string is in alphabetical
// order or not
static boolean isAlphabaticOrder(String s)
{
// length of the string
int n = s.length();
// create a character array
// of the length of the string
char c[] = new char [n];
// assign the string
// to character array
for (int i = 0; i < n; i++) {
c[i] = s.charAt(i);
}
// sort the character array
Arrays.sort(c);
// check if the character array
// is equal to the string or not
for (int i = 0; i < n; i++)
if (c[i] != s.charAt(i))
return false;
return true;
}
public static void main(String args[])
{
String s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
System.out.println("Yes");
else
System.out.println("No");
}
// This Code is contributed by ANKITRAI1
}
Python3
# Python 3 implementation of above approach
# Function that checks whether
# the string is in alphabetical
# order or not
def isAlphabaticOrder(s):
# length of the string
n = len(s)
# create a character array
# of the length of the string
c = [s[i] for i in range(len(s))]
# sort the character array
c.sort(reverse = False)
# check if the character array
# is equal to the string or not
for i in range(n):
if (c[i] != s[i]):
return False
return True
# Driver code
if __name__ == '__main__':
s = "aabbbcc"
# check whether the string is
# in alphabetical order or not
if (isAlphabaticOrder(s)):
print("Yes")
else:
print("No")
# This code is contributed by
# Surendra_Gangwar
C#
// C# implementation of above approach
// import Arrays class
using System;
public class GFG{
// Function that checks whether
// the string is in alphabetical
// order or not
static bool isAlphabaticOrder(String s)
{
// length of the string
int n = s.Length;
// create a character array
// of the length of the string
char []c = new char [n];
// assign the string
// to character array
for (int i = 0; i < n; i++) {
c[i] = s[i];
}
// sort the character array
Array.Sort(c);
// check if the character array
// is equal to the string or not
for (int i = 0; i < n; i++)
if (c[i] != s[i])
return false;
return true;
}
static public void Main (){
String s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
Console.WriteLine("Yes");
else
Console.WriteLine("No");
}
}
PHP
<?php
// PHP implementation of above approach
// Function that checks whether
// the string is in alphabetical
// order or not
Function isAlphabaticOrder($s)
{
// length of the string
$n = strlen($s);
$c = array();
// assign the string
// to character array
for ($i = 0; $i < $n; $i++)
{
$c[$i] = $s[$i];
}
// sort the character array
sort($c);
// check if the character array
// is equal to the string or not
for ($i = 0; $i < $n; $i++)
if ($c[$i] != $s[$i])
return false;
return true;
}
// Driver code
$s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder($s))
echo "Yes";
else
echo "No";
// This Code is contributed
// by Shivi_Aggarwal
?>
Javascript
<script>
//Javascript implementation of above approach
// Function that checks whether
// the string is in alphabetical
// order or not
function isAlphabaticOrder(s)
{
// length of the string
var n = s.length;
// create a character array
// of the length of the string
var c = new Array(n);
// assign the string
// to character array
for (var i = 0; i < n; i++) {
c[i] = s[i];
}
// sort the character array
c.sort();
// check if the character array
// is equal to the string or not
for (var i = 0; i < n; i++)
if (c[i] != s[i])
return false;
return true;
}
s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
document.write( "Yes");
else
document.write( "No");
//This code is contributed by SoumikMondal
</script>
Producción:
Yes
Complejidad del tiempo: O(N*log(N))
Espacio Auxiliar: O(N)
Aproximación Eficiente:
- Ejecute un ciclo de 1 a (n-1) (donde n es la longitud de la string)
- Compruebe si el elemento en el índice ‘i’ es menor que el elemento en el índice ‘i-1’.
- En caso afirmativo, escriba ‘En orden alfabético’.
- Imprima ‘No en orden alfabético’ de lo contrario.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function that checks whether
// the string is in alphabetical
// order or not
bool isAlphabaticOrder(string s)
{
int n = s.length();
for (int i = 1; i < n; i++) {
// if element at index 'i' is less
// than the element at index 'i-1'
// then the string is not sorted
if (s[i] < s[i - 1])
return false;
}
return true;
}
// Driver code
int main()
{
string s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of above approach
public class GFG {
// Function that checks whether
// the string is in alphabetical
// order or not
static boolean isAlphabaticOrder(String s) {
int n = s.length();
for (int i = 1; i < n; i++) {
// if element at index 'i' is less
// than the element at index 'i-1'
// then the string is not sorted
if (s.charAt(i) < s.charAt(i - 1)) {
return false;
}
}
return true;
}
// Driver code
static public void main(String[] args) {
String s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s)) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
}
//This code is contributed by PrinciRaj1992
Python 3
# Python 3 implementation of above approach
# Function that checks whether
# the string is in alphabetical
# order or not
def isAlphabaticOrder(s):
n = len(s)
for i in range(1, n):
# if element at index 'i' is less
# than the element at index 'i-1'
# then the string is not sorted
if (s[i] < s[i - 1]) :
return False
return True
# Driver code
if __name__ == "__main__":
s = "aabbbcc"
# check whether the string is
# in alphabetical order or not
if (isAlphabaticOrder(s)):
print("Yes")
else:
print("No")
C#
// C# implementation of above approach
using System;
public class GFG{
// Function that checks whether
// the string is in alphabetical
// order or not
static bool isAlphabaticOrder(string s)
{
int n = s.Length;
for (int i = 1; i < n; i++) {
// if element at index 'i' is less
// than the element at index 'i-1'
// then the string is not sorted
if (s[i] < s[i - 1])
return false;
}
return true;
}
// Driver code
static public void Main (){
string s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
Console.WriteLine ("Yes");
else
Console.WriteLine ("No");
}
}
PHP
<?php
// PHP implementation of above approach
// Function that checks whether
// the string is in alphabetical
// order or not
function isAlphabaticOrder($s)
{
$n = strlen($s);
for ($i = 1; $i < $n; $i++)
{
// if element at index 'i' is less
// than the element at index 'i-1'
// then the string is not sorted
if ($s[$i] < $s[$i - 1])
return false;
}
return true;
}
// Driver code
$s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder($s))
echo "Yes";
else
echo "No";
// This code is contributed
// by Sach_Code
?>
Javascript
<script>
// JavaScript implementation of above approach
// Function that checks whether
// the string is in alphabetical
// order or not
function isAlphabaticOrder( s){
let n = s.length;
for (let i = 1; i < n; i++) {
// if element at index 'i' is less
// than the element at index 'i-1'
// then the string is not sorted
if (s[i] < s[i - 1])
return false;
}
return true;
}
// Driver code
let s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
document.write("Yes");
else
document.write("No");
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Otro enfoque eficiente:
Los pasos involucrados son los siguientes:
- Itere a través de la string dada y almacene el conteo de frecuencia de cada alfabeto.
- Luego itere a través de cada alfabeto en orden lexicográfico creciente (de la a a la z) y deje que el conteo de cualquier alfabeto sea x. Luego verifique si exactamente x elementos están presentes en la string dada en orden continuo o no.
- Si coincide con todos los alfabetos, devuelve verdadero; de lo contrario, devuelve falso.
Ejemplo ilustrativo:
Sea Str=”aabbccb”
Luego, el recuento de cada alfabeto es el siguiente { a = 2, b = 3 y c = 2}.
Ahora iteraremos a través de cada alfabeto y verificaremos la condición.
Como a=2, los primeros 2 elementos de la string deben ser ‘a’. Dado que hay 2 elementos con ‘a’ en la string dada, avanzaremos más.
Ahora b = 3, por lo que los siguientes 3 elementos deben ser ‘b’ en la string, que no está allí ya que el quinto elemento en la string dada no es ‘b’. Por lo tanto, la string no está en orden alfabético.
A continuación se muestra el código para el enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Function that checks whether
// the string is in alphabetical
// order or not
bool isAlphabaticOrder(string s)
{
// array to store the
// count of each alphabet
int arr[26]={0};
int n = s.length();
for(int i=0;i<n;i++)
{
arr[s[i]-'a']++;
}
int ind=0;
// Using the count array we will iterate
// in lexicographic order through each
// alphabet present and check if the
// string has element present in same
// order or not
for(int i=0;i<26;i++)
{
while(arr[i]--)
{
char c= char(97+i);
if(c!=s[ind])
{
return false;
}
else
{
ind++;
}
}
}
return true;
}
// Driver code
int main()
{
string s = "aabbbcc";
// check whether the string is
// in alphabetical order or not
if (isAlphabaticOrder(s))
cout << "Yes";
else
cout << "No";
return 0;
}
// This code is contributed by Pushpesh Raj.
Producción
Yes
Complejidad de tiempo: O(N)
Espacio auxiliar: O(1) ya que la array utilizada para contar la frecuencia de los alfabetos es de tamaño constante.
Publicación traducida automáticamente
Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA