Dada una string, escriba una función recursiva que verifique si la string dada es un palíndromo, de lo contrario, no un palíndromo.
Ejemplos:
Input : malayalam Output : Yes Reverse of malayalam is also malayalam. Input : max Output : No Reverse of max is not max.
Hemos discutido una función iterativa aquí .
La idea de una función recursiva es simple:
1) If there is only one character in string return true. 2) Else compare first and last characters and recur for remaining substring.
A continuación se muestra la implementación de la idea anterior:
C++
// A recursive C++ program to // check whether a given number // is palindrome or not #include <bits/stdc++.h> using namespace std; // A recursive function that // check a str[s..e] is // palindrome or not. bool isPalRec(char str[], int s, int e) { // If there is only one character if (s == e) return true; // If first and last // characters do not match if (str[s] != str[e]) return false; // If there are more than // two characters, check if // middle substring is also // palindrome or not. if (s < e + 1) return isPalRec(str, s + 1, e - 1); return true; } bool isPalindrome(char str[]) { int n = strlen(str); // An empty string is // considered as palindrome if (n == 0) return true; return isPalRec(str, 0, n - 1); } // Driver Code int main() { char str[] = "geeg"; if (isPalindrome(str)) cout << "Yes"; else cout << "No"; return 0; } // This code is contributed by shivanisinghss2110
C
// A recursive C program to // check whether a given number // is palindrome or not #include <stdio.h> #include <string.h> #include <stdbool.h> // A recursive function that // check a str[s..e] is // palindrome or not. bool isPalRec(char str[], int s, int e) { // If there is only one character if (s == e) return true; // If first and last // characters do not match if (str[s] != str[e]) return false; // If there are more than // two characters, check if // middle substring is also // palindrome or not. if (s < e + 1) return isPalRec(str, s + 1, e - 1); return true; } bool isPalindrome(char str[]) { int n = strlen(str); // An empty string is // considered as palindrome if (n == 0) return true; return isPalRec(str, 0, n - 1); } // Driver Code int main() { char str[] = "geeg"; if (isPalindrome(str)) printf("Yes"); else printf("No"); return 0; }
Java
// A recursive JAVA program to // check whether a given String // is palindrome or not import java.io.*; class GFG { // A recursive function that // check a str(s..e) is // palindrome or not. static boolean isPalRec(String str, int s, int e) { // If there is only one character if (s == e) return true; // If first and last // characters do not match if ((str.charAt(s)) != (str.charAt(e))) return false; // If there are more than // two characters, check if // middle substring is also // palindrome or not. if (s < e + 1) return isPalRec(str, s + 1, e - 1); return true; } static boolean isPalindrome(String str) { int n = str.length(); // An empty string is // considered as palindrome if (n == 0) return true; return isPalRec(str, 0, n - 1); } // Driver Code public static void main(String args[]) { String str = "geeg"; if (isPalindrome(str)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed // by Nikita Tiwari
Python
# A recursive Python program # to check whether a given # number is palindrome or not # A recursive function that # check a str[s..e] is # palindrome or not. def isPalRec(st, s, e) : # If there is only one character if (s == e): return True # If first and last # characters do not match if (st[s] != st[e]) : return False # If there are more than # two characters, check if # middle substring is also # palindrome or not. if (s < e + 1) : return isPalRec(st, s + 1, e - 1); return True def isPalindrome(st) : n = len(st) # An empty string is # considered as palindrome if (n == 0) : return True return isPalRec(st, 0, n - 1); # Driver Code st = "geeg" if (isPalindrome(st)) : print "Yes" else : print "No" # This code is contributed # by Nikita Tiwari.
C#
// A recursive C# program to // check whether a given number // is palindrome or not using System; class GFG { // A recursive function that // check a str(s..e) // is palindrome or not. static bool isPalRec(String str, int s, int e) { // If there is only one character if (s == e) return true; // If first and last character // do not match if ((str[s]) != (str[e])) return false; // If there are more than two // characters, check if middle // substring is also // palindrome or not. if (s < e + 1) return isPalRec(str, s + 1, e - 1); return true; } static bool isPalindrome(String str) { int n = str.Length; // An empty string is considered // as palindrome if (n == 0) return true; return isPalRec(str, 0, n - 1); } // Driver Code public static void Main() { String str = "geeg"; if (isPalindrome(str)) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by Nitin Mittal.
PHP
<?php // A recursive php program to // check whether a given number // is palindrome or not // A recursive function that // check a str[s..e] is // palindrome or not. function isPalRec($str, $s,$e) { // If there is only one character if ($s == $e) return true; // If first and last // characters do not match if ($str[$s] != $str[$e]) return false; // If there are more than two // characters, check if middle // substring is also palindrome or not. if ($s < $e + 1) return isPalRec($str, $s + 1, $e - 1); return true; } function isPalindrome($str) { $n = strlen($str); // An empty string is // considered as palindrome if ($n == 0) return true; return isPalRec($str, 0, $n - 1); } // Driver Code { $str = "geeg"; if (isPalindrome($str)) echo("Yes"); else echo("No"); return 0; } // This code is contributed // by nitin mittal. ?>
Javascript
<script> // A recursive javascript program to // check whether a given String // is palindrome or not // A recursive function that // check a str(s..e) is // palindrome or not. function isPalRec( str , s , e) { // If there is only one character if (s == e) return true; // If first and last // characters do not match if ((str.charAt(s)) != (str.charAt(e))) return false; // If there are more than // two characters, check if // middle substring is also // palindrome or not. if (s < e + 1) return isPalRec(str, s + 1, e - 1); return true; } function isPalindrome( str) { var n = str.length; // An empty string is // considered as palindrome if (n == 0) return true; return isPalRec(str, 0, n - 1); } // Driver Code var str = "geeg"; if (isPalindrome(str)) document.write("Yes"); else document.write("No"); // This code contributed by gauravrajput1 </script>
Yes
Otro enfoque :
Básicamente, mientras atraviesa, verifique si el índice i-th y ni-1th son iguales o no.
Si no son iguales devuelve falso y si son iguales entonces continúa con las llamadas de recurrencia.
C++
#include <iostream> using namespace std; bool isPalindrome(string s, int i){ if(i > s.size()/2){ return true ; } return s[i] == s[s.size()-i-1] && isPalindrome(s, i+1) ; } int main() { string str = "geeg" ; if (isPalindrome(str, 0)) cout << "Yes"; else cout << "No"; return 0; }
Java
/*package whatever //do not write package name here */ import java.io.*; class GFG { public static boolean isPalindrome(String s, int i){ if(i > s.length()/2) { return true ; } return s.charAt(i) == s.charAt(s.length()-i-1) && isPalindrome(s, i+1) ; } public static void main (String[] args) { String str = "geeg" ; if (isPalindrome(str, 0)) { System.out.println("Yes"); } else { System.out.println("No"); } } } // This code is contributed by akashish.
C#
using System; public class GFG{ public static bool isPalindrome(string s, int i){ if(i > s.Length/2){ return true ; } return s[i] == s[s.Length-i-1] && isPalindrome(s, i+1) ; } public static void Main (){ // Code string str = "geeg" ; if (isPalindrome(str, 0)) { Console.WriteLine("Yes"); } else { Console.WriteLine("No"); } } } // This code is contributed by akashish_.
Javascript
<script> function isPalindrome(s,i){ if(i > s.length/2) {return true;} return s[i] == s[s.length-i-1] && isPalindrome(s, i+1) } let str = "geeg"; let ans = isPalindrome(str, 0); if (ans == true) { console.log("Yes");} else { console.log("No");} // This code is contributed by akashish__ </script>
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Sahil Rajput . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA