用于检查字符串是否为回文的递归函数

给定一个字符串,编写一个递归函数,检查给定字符串是否为回文,否则为非回文。

null

例如:

Input : malayalamOutput : YesReverse of malayalam is alsomalayalam.Input : maxOutput : NoReverse of max is not max. 

我们讨论了一个迭代函数 在这里 . 递归函数的概念很简单:

1) If there is only one character in string   return true.2) Else compare first and last characters   and recur for remaining substring.

以下是上述理念的实施情况:

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

另一种方法:

基本上在遍历时检查第i个和第n-i-1个索引是否相等。

如果不存在equal return false,如果它们相等,则继续递归调用。

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;
}


输出

Yes

时间复杂性: O(n)

辅助空间: O(n)

本文由 萨希尔·拉吉普特 .如果你喜欢GeekSforgek,并想贡献自己的力量,你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上,并帮助其他极客。 如果您发现任何不正确的地方,或者您想分享有关上述主题的更多信息,请写下评论。

© 版权声明
THE END
喜欢就支持一下吧
点赞15 分享