Dada una string que representa una oración llamada str de tamaño N , la tarea es encontrar todas las palabras válidas en una oración que están ordenadas lexicográficamente en orden creciente y decreciente junto con sus conteos.
Nota: Las palabras válidas son:-
- palabras que no contienen números.
- palabras mayores que tamaño 1 .
Ejemplos:
Entrada: str=”geeks for geeks”
Salida:
1 “for”
0
Explicación: “for” es una palabra que se ordena lexicográficamente en orden creciente (1). No hay ninguna palabra ordenada lexicográficamente en orden decreciente (0).Entrada: str=”Ganamos el partido por 4 carreras”
Salida:
1 “por”
3 “nosotros”, “ganamos”, “el”
Explicación: “por” se ordena en orden creciente (1) mientras que “nosotros”, “ won” y “the” se ordenan lexicográficamente en orden decreciente(3).
Enfoque: La idea de recorrer la string palabra por palabra y verificar para cada palabra si es lexicográficamente creciente o lexicográficamente decreciente. Imprima cada palabra según el tipo encontrado.
Siga los pasos a continuación para conocer el enfoque en detalle:
- Primero recorra las palabras en una string dada y cuente el número de palabras lexicográficamente crecientes y lexicográficamente decrecientes, en count1 y count2 respectivamente.
- Ahora primero imprima el recuento de palabras lexicográficamente crecientes almacenadas en count1
- Luego recorra la string palabra por palabra e imprima todas las palabras lexicográficamente crecientes.
- Repita los dos últimos pasos para palabras lexicográficamente decrecientes.
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 string is
// sorted in increasing order
bool issorted(string s)
{
// using transform() function and ::tolower in STL
transform(s.begin(), s.end(), s.begin(), ::tolower);
for (int i = 0; i < s.size() - 1; i++) {
if (s[i] > s[i + 1] or isdigit(s[i])) {
return false;
}
}
return true;
}
// Function to check ifstring is
// sorted in decreasing order
bool issortedre(string s)
{
// using transform() function and ::tolower in STL
transform(s.begin(), s.end(), s.begin(), ::tolower);
for (int i = 0; i < s.size() - 1; i++) {
if (s[i] < s[i + 1] or isdigit(s[i])) {
return false;
}
}
return true;
}
// Function to count
// the required absolute difference
void count(string s)
{
stringstream ss(s);
string word;
int count1 = 0, count2 = 0;
// Checking validity of word
while (ss >> word) {
if (word.size() == 1)
continue;
// Counting the valid words
// in increasing order
if (issorted(word)) {
count1++;
}
// Counting the valid words
// in decreasing order
else if (issortedre(word)) {
count2++;
}
}
stringstream ss1(s);
// Printing count of
// lexicographically increasing words
cout << count1 << " ";
// Print all lexicographically
// increasing words
while (ss1 >> word) {
if (word.size() == 1)
continue;
// Printing all valid words
// in increasing order
if (issorted(word)) {
cout << "\"" << word << "\" ";
}
}
cout << endl;
stringstream ss2(s);
// Printing count of
// lexicographically increasing words
cout << count2 << " ";
// Print all lexicographically
// increasing words
while (ss2 >> word) {
if (word.size() == 1)
continue;
// Printing all valid words
// in decreasing order
else if (issortedre(word)) {
cout << "\"" << word << "\" ";
}
}
cout << endl;
}
// Driver Code
int main()
{
string s = "We won the match by 4 runs";
count(s);
return 0;
}
Java
// Java program for the above approach
class GFG {
static boolean isdigit(char c) {
return c >= '0' && c <= '9';
}
// Function to check if String is
// sorted in increasing order
public static boolean issorted(String s)
{
// using transform() function and ::tolower in STL
s = s.toLowerCase();
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) > s.charAt(i + 1) || isdigit(s.charAt(i))) {
return false;
}
}
return true;
}
// Function to check ifString is
// sorted in decreasing order
public static boolean issortedre(String s)
{
// using transform() function and ::tolower in STL
s = s.toLowerCase();
for (int i = 0; i < s.length() - 1; i++) {
if (s.charAt(i) < s.charAt(i + 1) || isdigit(s.charAt(i))) {
return false;
}
}
return true;
}
// Function to count
// the required absolute difference
public static void count(String s) {
String[] ss = s.split(" ");
String word;
int count1 = 0, count2 = 0;
// Checking validity of word
for (int i = 0; i < ss.length; i++) {
word = ss[i];
if (word.length() == 1)
continue;
// Counting the valid words
// in increasing order
if (issorted(word)) {
count1++;
}
// Counting the valid words
// in decreasing order
else if (issortedre(word)) {
count2++;
}
}
String[] ss1 = s.split(" ");
// Printing count of
// lexicographically increasing words
System.out.print(count1 + " ");
// Print all lexicographically
// increasing words
for (int i = 0; i < ss1.length; i++) {
word = ss1[i];
if (word.length() == 1)
continue;
// Printing all valid words
// in increasing order
if (issorted(word)) {
System.out.print("\"" + word + "\" ");
}
}
System.out.println();
String[] ss2 = s.split(" ");
// Printing count of
// lexicographically increasing words
System.out.print(count2 + " ");
// Print all lexicographically
// increasing words
for (int i = 0; i < ss2.length; i++) {
word = ss2[i];
if (word.length() == 1)
continue;
// Printing all valid words
// in decreasing order
else if (issortedre(word)) {
System.out.print("\"" + word + "\" ");
}
}
System.out.println();
}
// Driver Code
public static void main(String args[]) {
String s = "We won the match by 4 runs";
count(s);
}
}
// This code is contributed by gfgking.
Python3
# Python Program to implement
# the above approach
def isCharNumber(c):
return c >= '0' and c <= '9'
# Function to check if string is
# sorted in increasing order
def issorted(s):
# using transform() function and ::tolower in STL
s = s.lower()
for i in range(len(s) - 1):
if (ord(s[i]) > ord(s[i + 1]) or isCharNumber(s[i])):
return False
return True
# Function to check ifstring is
# sorted in decreasing order
def issortedre(s):
# using transform() function and ::tolower in STL
s = s.lower()
for i in range(len(s) - 1):
if (ord(s[i]) < ord(s[i + 1]) or isCharNumber(s[i])):
return False
return True
# Function to count
# the required absolute difference
def count(s):
word = ""
count1 = 0
count2 = 0
ss = s.split(" ")
# Checking validity of word
for i in range(len(ss)):
word = ss[i]
if (len(word) == 1):
continue
# Counting the valid words
# in increasing order
if (issorted(word)):
count1 += 1
# Counting the valid words
# in decreasing order
elif (issortedre(word)):
count2 += 1
# Printing count of
# lexicographically increasing words
print(count1, end=" ")
# Print all lexicographically
# increasing words
for i in range(len(ss)):
word = ss[i]
if (len(word) == 1):
continue
# Printing all valid words
# in increasing order
if (issorted(word)):
print(f" {word} ")
# Printing count of
# lexicographically increasing words
print(count2, end=" ")
# Print all lexicographically
# increasing words
for i in range(len(ss)):
word = ss[i]
if (len(word) == 1):
continue
# Printing all valid words
# in decreasing order
elif (issortedre(word)):
print(f" {word} ", end=" ")
# Driver Code
s = "We won the match by 4 runs"
count(s)
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG{
static bool isdigit(char c)
{
return c >= '0' && c <= '9';
}
// Function to check if String is
// sorted in increasing order
public static bool issorted(String s)
{
// Using transform() function and ::tolower in STL
s = s.ToLower();
for(int i = 0; i < s.Length - 1; i++)
{
if (s[i] > s[i + 1] || isdigit(s[i]))
{
return false;
}
}
return true;
}
// Function to check ifString is
// sorted in decreasing order
public static bool issortedre(String s)
{
// Using transform() function and ::tolower in STL
s = s.ToLower();
for(int i = 0; i < s.Length - 1; i++)
{
if (s[i] < s[i + 1] || isdigit(s[i]))
{
return false;
}
}
return true;
}
// Function to count the
// required absolute difference
public static void count(String s)
{
String[] ss = s.Split(' ');
String word;
int count1 = 0, count2 = 0;
// Checking validity of word
for(int i = 0; i < ss.Length; i++)
{
word = ss[i];
if (word.Length == 1)
continue;
// Counting the valid words
// in increasing order
if (issorted(word))
{
count1++;
}
// Counting the valid words
// in decreasing order
else if (issortedre(word))
{
count2++;
}
}
String[] ss1 = s.Split(' ');
// Printing count of lexicographically
// increasing words
Console.Write(count1 + " ");
// Print all lexicographically
// increasing words
for(int i = 0; i < ss1.Length; i++)
{
word = ss1[i];
if (word.Length == 1)
continue;
// Printing all valid words
// in increasing order
if (issorted(word))
{
Console.Write("\"" + word + "\" ");
}
}
Console.WriteLine();
String[] ss2 = s.Split(' ');
// Printing count of lexicographically
// increasing words
Console.Write(count2 + " ");
// Print all lexicographically
// increasing words
for(int i = 0; i < ss2.Length; i++)
{
word = ss2[i];
if (word.Length == 1)
continue;
// Printing all valid words
// in decreasing order
else if (issortedre(word))
{
Console.Write("\"" + word + "\" ");
}
}
Console.WriteLine();
}
// Driver Code
public static void Main(String []args)
{
String s = "We won the match by 4 runs";
count(s);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript Program to implement
// the above approach
function isCharNumber(c) {
return c >= '0' && c <= '9';
}
// Function to check if string is
// sorted in increasing order
function issorted(s)
{
// using transform() function and ::tolower in STL
s = s.toLowerCase()
for (let i = 0; i < s.length - 1; i++) {
if (s[i].charCodeAt(0) > s[i + 1].charCodeAt(0) || isCharNumber(s[i])) {
return false;
}
}
return true;
}
// Function to check ifstring is
// sorted in decreasing order
function issortedre(s)
{
// using transform() function and ::tolower in STL
s = s.toLowerCase();
for (let i = 0; i < s.length - 1; i++) {
if (s[i].charCodeAt(0) < s[i + 1].charCodeAt(0) || isCharNumber(s[i])) {
return false;
}
}
return true;
}
// Function to count
// the required absolute difference
function count(s) {
let word;
let count1 = 0, count2 = 0;
let ss = s.split(" ");
// Checking validity of word
for (let i = 0; i < ss.length; i++) {
word = ss[i]
if (word.length == 1)
continue;
// Counting the valid words
// in increasing order
if (issorted(word)) {
count1++;
}
// Counting the valid words
// in decreasing order
else if (issortedre(word)) {
count2++;
}
}
// Printing count of
// lexicographically increasing words
document.write(count1 + " ");
// Print all lexicographically
// increasing words
for (let i = 0; i < ss.length; i++) {
word = ss[i];
if (word.length == 1)
continue;
// Printing all valid words
// in increasing order
if (issorted(word)) {
document.write(" " + word + " ")
}
}
document.write('<br>');
// Printing count of
// lexicographically increasing words
document.write(count2 + " ");
// Print all lexicographically
// increasing words
for (let i = 0; i < ss.length; i++) {
word = ss[i];
if (word.length == 1)
continue;
// Printing all valid words
// in decreasing order
else if (issortedre(word)) {
document.write(" " + word + " ")
}
}
document.write('<br>');
}
// Driver Code
let s = "We won the match by 4 runs";
count(s);
// This code is contributed by Potta Lokesh
</script>
Producción:
1 "by" 3 "We" "won" "the"
Complejidad de tiempo: O (N ^ 2), ya que estamos usando bucles anidados para atravesar N * N veces.
Espacio Auxiliar: O(N), ya que estamos usando espacio extra.
Publicación traducida automáticamente
Artículo escrito por shreyanshgupta838 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA