Compruebe si los caracteres de cada palabra se pueden reorganizar para formar una progresión aritmética (AP)

Dada la string str , la tarea es comprobar si es posible reorganizar la string de modo que los caracteres de cada palabra de la string dada estén en progresión aritmética .

Ejemplos:

Entrada: str = “ace yzx fbd”
Salida: verdadero
Explicación: Reorganizar la string dada a “ace xyz bdf”.
Todos los caracteres de la palabra “ace” están en AP con una diferencia común de 2.
Todos los caracteres de la palabra “xyz” están en AP con una diferencia común de 1
Todos los caracteres de la palabra “bdf” están en AP con una diferencia común de 2.
Por lo tanto, la salida requerida es verdadera.

Entrada: str = «geeks para geeks»
Salida: falso

Enfoque: La idea es ordenar cada palabra de la string dada y verificar si la diferencia entre los caracteres adyacentes en todas las palabras es igual o no. Si se encuentra que es cierto, escriba Sí . De lo contrario , imprima No. Siga los pasos a continuación para resolver el problema.

1. Itere sobre la string str y divida cada palabra de str por un delimitador de espacio.
2. Ordene cada palabra de la string dada en orden ascendente .
3. Compruebe si la diferencia entre todos los caracteres adyacentes de las palabras es igual.
4. Si se encuentra que es cierto, escriba Sí . De lo contrario , imprima No.

A continuación se muestra la implementación del enfoque anterior:

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check str can be
// rearranged such that characters
// of each word forms an AP
 
int checkWordAP(string str)
{
    // Stores the string
    // in stringstream
    stringstream ss(str);
 
    // Stores each word of
    // the given string
    string temp;
    while (getline(ss, temp, ' ')) {
        // Sort the current word
        sort(temp.begin(), temp.end());
 
        // Check if the current word
        // of the given string is in AP
        for (int i = 2; i < temp.length();
             i++) {
            // Store the value of difference
            // between adjacent characters
            int diff = temp[1] - temp[0];
 
            // Check if difference between all
            // adjacent characters are equal
            if (diff != temp[i] - temp[i - 1]) {
                return false;
            }
        }
    }
 
    // If all words are in AP.
    return true;
}
 
// Driver Code
int main()
{
    string str = "ace yzx fbd";
 
    // If all words of the given
    // string are in AP
    if (checkWordAP(str)) {
        cout << "Yes";
    }
    else {
        cout << "No";
    }
}

// Java program to implement
// the above approach
import java.util.*;
class GFG{
 
// Function to check str can be
// rearranged such that characters
// of each word forms an AP
static boolean checkWordAP(String s)
{
  // Stores the String
  // in Stringstream
  String str[] = s.split(" ");
 
  // Stores each word of
  // the given String
 
  for (String temp : str )
  {
    // Sort the current word
    temp = sort(temp);
 
    // Check if the current word
    // of the given String is in AP
    for (int i = 2; i < temp.length(); i++)
    {
      // Store the value of difference
      // between adjacent characters
      int diff = temp.charAt(1) - temp.charAt(0);
 
      // Check if difference between all
      // adjacent characters are equal
      if (diff != temp.charAt(i) - temp.charAt(i - 1))
      {
        return false;
      }
    }
  }
 
  // If all words are in AP.
  return true;
}
   
static String sort(String inputString)
{
  // convert input string to char array
  char tempArray[] = inputString.toCharArray();
 
  // sort tempArray
  Arrays.sort(tempArray);
 
  // return new sorted string
  return new String(tempArray);
}
 
// Driver Code
public static void main(String[] args)
{
  String str = "ace yzx fbd";
 
  // If all words of the given
  // String are in AP
  if (checkWordAP(str))
  {
    System.out.print("Yes");
  }
  else
  {
    System.out.print("No");
  }
}
}
 
// This code is contributed by Princi Singh

# Python3 program to implement
# the above approach
 
# Function to check st can be
# rearranged such that characters
# of each word forms an AP
def checkWordAP(st):
 
    # Stores each word of
    # the given string
    st = st.split(" ")
     
    for temp in st:
         
        # Sort the current word
        temp = sorted(temp)
 
        # Check if the current word
        # of the given is in AP
        for i in range(2, len(temp)):
             
            # Store the value of difference
            # between adjacent characters
            diff = ord(temp[1]) - ord(temp[0])
 
            # Check if difference between all
            # adjacent characters are equal
            if (diff != ord(temp[i]) -
                        ord(temp[i - 1])):
                return False
 
    # If all words are in AP.
    return True
 
# Driver Code
if __name__ == '__main__':
     
    st = "ace yzx fbd"
 
    # If all words of the given
    # are in AP
    if (checkWordAP(st)):
        print("Yes")
    else:
        print("No")
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to check str can be
// rearranged such that characters
// of each word forms an AP
static bool checkWordAP(String s)
{
  // Stores the String
  // in Stringstream
  String []str = s.Split(' ');
 
  // Stores each word of
  // the given String
  String temp = "";
  foreach (String temp1 in str )
  {
    // Sort the current word
    temp = sort(temp1);
 
    // Check if the current word
    // of the given String is in AP
    for (int i = 2; i < temp.Length; i++)
    {
      // Store the value of difference
      // between adjacent characters
      int diff = temp[1] - temp[0];
 
      // Check if difference between all
      // adjacent characters are equal
      if (diff != temp[i] - temp[i - 1])
      {
        return false;
      }
    }
  }
 
  // If all words are in AP.
  return true;
}
   
static String sort(String inputString)
{
  // convert input string to char array
  char []tempArray = inputString.ToCharArray();
 
  // sort tempArray
  Array.Sort(tempArray);
 
  // return new sorted string
  return new String(tempArray);
}
 
// Driver Code
public static void Main(String[] args)
{
  String str = "ace yzx fbd";
 
  // If all words of the given
  // String are in AP
  if (checkWordAP(str))
  {
    Console.Write("Yes");
  }
  else
  {
    Console.Write("No");
  }
}
}
 
// This code is contributed by Princi Singh

<script>
// Javascript program to implement
// the above approach
 
// Function to check str can be
// rearranged such that characters
// of each word forms an AP
function checkWordAP(s)
{
 
    // Stores the String
  // in Stringstream
  let str = s.split(" ");
  
  // Stores each word of
  // the given String
  
  for (let temp = 0; temp < str.length; temp++ )
  {
   
    // Sort the current word
    str[temp] = sort(str[temp]);
  
    // Check if the current word
    // of the given String is in AP
    for (let i = 2; i < str[temp].length; i++)
    {
     
      // Store the value of difference
      // between adjacent characters
      let diff = str[temp][1].charCodeAt(0) - str[temp][0].charCodeAt(0);
  
      // Check if difference between all
      // adjacent characters are equal
      if (diff != str[temp][i].charCodeAt(0) - str[temp][i-1].charCodeAt(0))
      {
        return false;
      }
    }
  }
  
  // If all words are in AP.
  return true;
}
 
function sort(inputString)
{
 
    // convert input string to char array
  let tempArray = inputString.split("");
  
  // sort tempArray
  (tempArray).sort();
  
  // return new sorted string
  return (tempArray).join("");
}
 
// Driver Code
let str = "ace yzx fbd";
  
  // If all words of the given
  // String are in AP
  if (checkWordAP(str))
  {
    document.write("Yes");
  }
  else
  {
    document.write("No");
  }
 
// This code is contributed by patel2127
</script>

Yes

Complejidad de Tiempo: O(N log ₂ N)
Espacio Auxiliar: O(N)