给定一个字符串,编写一个递归函数,检查给定字符串是否为回文,否则为非回文。
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