String dada str . La string puede contener letras minúsculas, caracteres especiales, dígitos o incluso espacios en blanco . La tarea es verificar si solo las letras presentes en la string forman una combinación palindrómica o no sin usar ningún espacio adicional.
Nota : No está permitido usar espacio adicional para resolver este problema. Además, las letras presentes en la string están en minúsculas y la string puede contener caracteres especiales, dígitos o incluso espacios en blanco junto con letras minúsculas.
Ejemplos :
Entrada : str = “ma 343 la yal am”
Salida : YES
Los caracteres de la string forman la secuencia “malayalam”, que es un palíndromo.Entrada : str = «malayalam»
Salida : SÍ
Enfoque :
- Cree dos funciones de utilidad para obtener la primera y la última posición de los caracteres presentes en la string.
- Comience a recorrer la string y siga encontrando la posición del primer y último carácter cada vez.
- Si el primer y el último carácter son los mismos para cada iteración y la string se recorre por completo, imprima SÍ; de lo contrario, imprima NO.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to check if the characters in
// the given string forms a Palindrome in
// O(1) extra space
#include <iostream>
using namespace std;
// Utility function to get the position of
// first character in the string
int firstPos(string str, int start, int end)
{
int firstChar = -1;
// Get the position of first character
// in the string
for (int i = start; i <= end; i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
firstChar = i;
break;
}
}
return firstChar;
}
// Utility function to get the position of
// last character in the string
int lastPos(string str, int start, int end)
{
int lastChar = -1;
// Get the position of last character
// in the string
for (int i = start; i >= end; i--) {
if (str[i] >= 'a' && str[i] <= 'z') {
lastChar = i;
break;
}
}
return lastChar;
}
// Function to check if the characters in
// the given string forms a Palindrome in
// O(1) extra space
bool isPalindrome(string str)
{
int firstChar = 0, lastChar = str.length() - 1;
bool ch = true;
for (int i = 0; i < str.length(); i++) {
firstChar = firstPos(str, firstChar, lastChar);
lastChar = lastPos(str, lastChar, firstChar);
// break, when all letters are checked
if (lastChar < 0 || firstChar < 0)
break;
if (str[firstChar] == str[lastChar]) {
firstChar++;
lastChar--;
continue;
}
// if mismatch found, break the loop
ch = false;
break;
}
return (ch);
}
// Driver code
int main()
{
string str = "m a 343 la y a l am";
if (isPalindrome(str))
cout << "YES";
else
cout << "NO";
return 0;
}
Java
// Java program to check if
// the characters in the given
// string forms a Palindrome
// in O(1) extra space
import java.io.*;
class GFG
{
// Utility function to get
// the position of first
// character in the string
static int firstPos(String str,
int start,
int end)
{
int firstChar = -1;
// Get the position of
// first character in
// the string
for(int i = start; i <= end; i++)
{
if(str.charAt(i) >= 'a'&&
str.charAt(i) <= 'z')
{
firstChar = i;
break;
}
}
return firstChar;
}
// Utility function to get
// the position of last
// character in the string
static int lastPos(String str,
int start,
int end)
{
int lastChar = -1;
// Get the position of last
// character in the string
for(int i = start; i >= end; i--)
{
if(str.charAt(i) >= 'a'&&
str.charAt(i) <= 'z')
{
lastChar = i;
break;
}
}
return lastChar;
}
// Function to check if the
// characters in the given
// string forms a Palindrome
// in O(1) extra space
static boolean isPalindrome(String str)
{
int firstChar = 0,
lastChar = str.length() - 1;
boolean ch = true;
for (int i = 0; i < str.length(); i++)
{
firstChar = firstPos(str, firstChar,
lastChar);
lastChar = lastPos(str, lastChar,
firstChar);
// break, when all
// letters are checked
if (lastChar < 0 || firstChar < 0)
break;
if (str.charAt(firstChar) ==
str.charAt(lastChar))
{
firstChar++;
lastChar--;
continue;
}
// if mismatch found,
// break the loop
ch = false;
break;
}
return ch;
}
// Driver code
public static void main (String[] args)
{
String str = "m a 343 la y a l am";
if(isPalindrome(str))
System.out.print("YES");
else
System.out.println("NO");
}
}
// This code is contributed
// by inder_verma.
Python 3
# Python 3 program to check if the characters
# in the given string forms a Palindrome in
# O(1) extra space
# Utility function to get the position of
# first character in the string
def firstPos(str, start, end):
firstChar = -1
# Get the position of first character
# in the string
for i in range(start, end + 1):
if (str[i] >= 'a' and str[i] <= 'z') :
firstChar = i
break
return firstChar
# Utility function to get the position of
# last character in the string
def lastPos(str, start, end):
lastChar = -1
# Get the position of last character
# in the string
for i in range(start, end - 1, -1) :
if (str[i] >= 'a' and str[i] <= 'z') :
lastChar = i
break
return lastChar
# Function to check if the characters in
# the given string forms a Palindrome in
# O(1) extra space
def isPalindrome(str):
firstChar = 0
lastChar = len(str) - 1
ch = True
for i in range(len(str)) :
firstChar = firstPos(str, firstChar, lastChar);
lastChar = lastPos(str, lastChar, firstChar);
# break, when all letters are checked
if (lastChar < 0 or firstChar < 0):
break
if (str[firstChar] == str[lastChar]):
firstChar += 1
lastChar -= 1
continue
# if mismatch found, break the loop
ch = False
break
return (ch)
# Driver code
if __name__ == "__main__":
str = "m a 343 la y a l am"
if (isPalindrome(str)):
print("YES")
else:
print("NO")
# This code is contributed by ita_c
C#
// C# program to check if
// the characters in the given
// string forms a Palindrome
// in O(1) extra space
using System;
class GFG
{
// Utility function to get
// the position of first
// character in the string
static int firstPos(string str,
int start,
int end)
{
int firstChar = -1;
// Get the position of
// first character in
// the string
for(int i = start; i <= end; i++)
{
if(str[i] >= 'a'&&
str[i] <= 'z')
{
firstChar = i;
break;
}
}
return firstChar;
}
// Utility function to get
// the position of last
// character in the string
static int lastPos(string str,
int start,
int end)
{
int lastChar = -1;
// Get the position of last
// character in the string
for(int i = start; i >= end; i--)
{
if(str[i] >= 'a'&&
str[i] <= 'z')
{
lastChar = i;
break;
}
}
return lastChar;
}
// Function to check if the
// characters in the given
// string forms a Palindrome
// in O(1) extra space
static bool isPalindrome(string str)
{
int firstChar = 0,
lastChar = str.Length - 1;
bool ch = true;
for (int i = 0; i < str.Length; i++)
{
firstChar = firstPos(str, firstChar,
lastChar);
lastChar = lastPos(str, lastChar,
firstChar);
// break, when all
// letters are checked
if (lastChar < 0 || firstChar < 0)
break;
if (str[firstChar] ==
str[lastChar])
{
firstChar++;
lastChar--;
continue;
}
// if mismatch found,
// break the loop
ch = false;
break;
}
return ch;
}
// Driver code
public static void Main ()
{
string str = "m a 343 la y a l am";
if(isPalindrome(str))
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed
// by inder_verma.
PHP
<?php
// PHP program to check if the
// characters in the given
// string forms a Palindrome
// in O(1) extra space
// Utility function to get the
// position of first character
// in the string
function firstPos($str, $start, $end)
{
$firstChar = -1;
// Get the position of first
// character in the string
for ($i = $start; $i <= $end; $i++)
{
if ($str[$i] >= 'a' and
$str[$i] <= 'z')
{
$firstChar = $i;
break;
}
}
return $firstChar;
}
// Utility function to get the
// position of last character
// in the string
function lastPos($str, $start, $end)
{
$lastChar = -1;
// Get the position of last
// character in the string
for ( $i = $start; $i >= $end; $i--)
{
if ($str[$i] >= 'a' and
$str[$i] <= 'z')
{
$lastChar = $i;
break;
}
}
return $lastChar;
}
// Function to check if the
// characters in the given
// string forms a Palindrome
// in O(1) extra space
function isPalindrome($str)
{
$firstChar = 0;
$lastChar = count($str) - 1;
$ch = true;
for ($i = 0; $i < count($str); $i++)
{
$firstChar = firstPos($str, $firstChar,
$lastChar);
$lastChar = lastPos($str, $lastChar,
$firstChar);
// break, when all letters are checked
if ($lastChar < 0 or $firstChar < 0)
break;
if ($str[$firstChar] == $str[$lastChar])
{
$firstChar++;
$lastChar--;
continue;
}
// if mismatch found,
// break the loop
$ch = false;
break;
}
return ($ch);
}
// Driver code
$str = "m a 343 la y a l am";
if (isPalindrome($str))
echo "YES";
else
echo "NO";
// This code is contributed
// by inder_verma.
?>
Javascript
<script>
// Javascript program to check if
// the characters in the given
// string forms a Palindrome
// in O(1) extra space
// Utility function to get
// the position of first
// character in the string
function firstPos(str,start,end)
{
let firstChar = -1;
// Get the position of
// first character in
// the string
for(let i = start; i <= end; i++)
{
if(str[i] >= 'a'&&
str[i] <= 'z')
{
firstChar = i;
break;
}
}
return firstChar;
}
// Utility function to get
// the position of last
// character in the string
function lastPos(str,start,end)
{
let lastChar = -1;
// Get the position of last
// character in the string
for(let i = start; i >= end; i--)
{
if(str[i] >= 'a'&&
str[i] <= 'z')
{
lastChar = i;
break;
}
}
return lastChar;
}
// Function to check if the
// characters in the given
// string forms a Palindrome
// in O(1) extra space
function isPalindrome(str)
{
let firstChar = 0,
lastChar = str.length - 1;
let ch = true;
for (let i = 0; i < str.length; i++)
{
firstChar = firstPos(str, firstChar,
lastChar);
lastChar = lastPos(str, lastChar,
firstChar);
// break, when all
// letters are checked
if (lastChar < 0 || firstChar < 0)
break;
if (str[firstChar] ==
str[lastChar])
{
firstChar++;
lastChar--;
continue;
}
// if mismatch found,
// break the loop
ch = false;
break;
}
return ch;
}
// Driver code
let str = "m a 343 la y a l am";
if(isPalindrome(str))
document.write("YES");
else
document.write("NO");
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
YES
Publicación traducida automáticamente
Artículo escrito por sjchatterjee_73 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA