La creazione di un metodo ricorsivo per Palindrome
https://stackoverflow.com/questions/4367260
-
09-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto cercando di creare un programma Palindrome utilizzando la ricorsione all'interno di Java, ma io sono bloccato, questo è quello che ho finora:
public static void main (String[] args){
System.out.println(isPalindrome("noon"));
System.out.println(isPalindrome("Madam I'm Adam"));
System.out.println(isPalindrome("A man, a plan, a canal, Panama"));
System.out.println(isPalindrome("A Toyota"));
System.out.println(isPalindrome("Not a Palindrome"));
System.out.println(isPalindrome("asdfghfdsa"));
}
public static boolean isPalindrome(String in){
if(in.equals(" ") || in.length() == 1 ) return true;
in= in.toUpperCase();
if(Character.isLetter(in.charAt(0))
}
public static boolean isPalindromeHelper(String in){
if(in.equals("") || in.length()==1){
return true;
}
}
}
Qualcuno può fornire una soluzione al mio problema?
Soluzione
Qui sto incollando il codice per voi:
Ma, vorrei vivamente di suggerire a sapere come funziona,
dalla tua domanda, si sono totalmente illeggibili.
Prova la comprensione di questo codice. Leggi i commenti da codice
import java.util.Scanner;
public class Palindromes
{
public static boolean isPal(String s)
{
if(s.length() == 0 || s.length() == 1)
// if length =0 OR 1 then it is
return true;
if(s.charAt(0) == s.charAt(s.length()-1))
// check for first and last char of String:
// if they are same then do the same thing for a substring
// with first and last char removed. and carry on this
// until you string completes or condition fails
return isPal(s.substring(1, s.length()-1));
// if its not the case than string is not.
return false;
}
public static void main(String[]args)
{
Scanner sc = new Scanner(System.in);
System.out.println("type a word to check if its a palindrome or not");
String x = sc.nextLine();
if(isPal(x))
System.out.println(x + " is a palindrome");
else
System.out.println(x + " is not a palindrome");
}
}
Altri suggerimenti
Bene:
- Non è chiaro il motivo per cui hai due metodi con la stessa firma. Quali sono intendevano compiere?
- Nel primo metodo, perché stai testando per testare per un singolo spazio o ogni singolo carattere?
- Si potrebbe prendere in considerazione generalizzando la sua condizione di terminazione a "se la lunghezza è inferiore a due"
- Pensate a come si desidera recurse. Una possibilità:
- Verificare che la prima lettera è uguale all'ultima lettera. In caso contrario, il ritorno false
- Ora prendete una stringa per rimuovere efficacemente la prima e l'ultima lettera, e recurse
- E 'questo vuole essere un esercizio di ricorsione? Questo è certamente una modo di farlo, ma è tutt'altro che l'unico modo.
Non ho intenzione di precisare fuori più chiaro di così, per il momento, perché ho il sospetto che questo è compito - anzi alcuni possono considerare l'aiuto di cui sopra come troppo (io sono certamente un po 'titubante me stesso). Se avete problemi con i suggerimenti di cui sopra, aggiornare la tua domanda per mostrare fino a che punto hai.
public static boolean isPalindrome(String in){
if(in.equals(" ") || in.length() < 2 ) return true;
if(in.charAt(0).equalsIgnoreCase(in.charAt(in.length-1))
return isPalindrome(in.substring(1,in.length-2));
else
return false;
}
Forse avete bisogno di qualcosa di simile. Non testato, io non sono sicuro di indici di stringa, ma è un punto di partenza.
Credo, la ricorsione non è il modo migliore per risolvere questo problema, ma in un modo ricorsivo che vedo qui è la seguente:
String str = prepareString(originalString); //make upper case, remove some characters
isPalindrome(str);
public boolean isPalindrome(String str) {
return str.length() == 1 || isPalindrome(str, 0);
}
private boolean isPalindrome(String str, int i) {
if (i > str.length / 2) {
return true;
}
if (!str.charAt(i).equals(str.charAt(str.length() - 1 - i))) {
return false;
}
return isPalindrome(str, i+1);
}
Ecco il mio andare a esso:
public class Test {
public static boolean isPalindrome(String s) {
return s.length() <= 1 ||
(s.charAt(0) == s.charAt(s.length() - 1) &&
isPalindrome(s.substring(1, s.length() - 1)));
}
public static boolean isPalindromeForgiving(String s) {
return isPalindrome(s.toLowerCase().replaceAll("[\\s\\pP]", ""));
}
public static void main(String[] args) {
// True (odd length)
System.out.println(isPalindrome("asdfghgfdsa"));
// True (even length)
System.out.println(isPalindrome("asdfggfdsa"));
// False
System.out.println(isPalindrome("not palindrome"));
// True (but very forgiving :)
System.out.println(isPalindromeForgiving("madam I'm Adam"));
}
}
public class palin
{
static boolean isPalin(String s, int i, int j)
{
boolean b=true;
if(s.charAt(i)==s.charAt(j))
{
if(i<=j)
isPalin(s,(i+1),(j-1));
}
else
{
b=false;
}
return b;
}
public static void main()
{
String s1="madam";
if(isPalin(s1, 0, s1.length()-1)==true)
System.out.println(s1+" is palindrome");
else
System.out.println(s1+" is not palindrome");
}
}
Alcuni dei codici sono stringa pesante. Invece di creare stringa che crea nuovo oggetto, possiamo solo passare indici in chiamate ricorsive come di seguito:
private static boolean isPalindrome(String str, int left, int right) {
if(left >= right) {
return true;
}
else {
if(str.charAt(left) == str.charAt(right)) {
return isPalindrome(str, ++left, --right);
}
else {
return false;
}
}
}
public static void main(String []args){
String str = "abcdcbb";
System.out.println(isPalindrome(str, 0, str.length()-1));
}
Ecco tre semplici implementazioni, in primo luogo l'oneliner:
public static boolean oneLinerPalin(String str){
return str.equals(new StringBuffer(str).reverse().toString());
}
Questa è naturalmente piuttosto lento in quanto crea uno StringBuffer ed inverte, e l'intera stringa viene sempre controllato nomatter se è un palindromo o no, ecco un'implementazione che controlla solo la quantità di caratteri richiesto e lo fa in luogo, in modo che nessun stringBuffers aggiuntivi:
public static boolean isPalindrome(String str){
if(str.isEmpty()) return true;
int last = str.length() - 1;
for(int i = 0; i <= last / 2;i++)
if(str.charAt(i) != str.charAt(last - i))
return false;
return true;
}
E in modo ricorsivo:
public static boolean recursivePalin(String str){
return check(str, 0, str.length() - 1);
}
private static boolean check (String str,int start,int stop){
return stop - start < 2 ||
str.charAt(start) == str.charAt(stop) &&
check(str, start + 1, stop - 1);
}
public static boolean isPalindrome(String str)
{
int len = str.length();
int i, j;
j = len - 1;
for (i = 0; i <= (len - 1)/2; i++)
{
if (str.charAt(i) != str.charAt(j))
return false;
j--;
}
return true;
}
Prova questo:
package javaapplicationtest;
public class Main {
public static void main(String[] args) {
String source = "mango";
boolean isPalindrome = true;
//looping through the string and checking char by char from reverse
for(int loop = 0; loop < source.length(); loop++){
if( source.charAt(loop) != source.charAt(source.length()-loop-1)){
isPalindrome = false;
break;
}
}
if(isPalindrome == false){
System.out.println("Not a palindrome");
}
else
System.out.println("Pailndrome");
}
}
String source = "liril";
StringBuffer sb = new StringBuffer(source);
String r = sb.reverse().toString();
if (source.equals(r)) {
System.out.println("Palindrome ...");
} else {
System.out.println("Not a palindrome...");
}
public class chkPalindrome{
public static String isPalindrome(String pal){
if(pal.length() == 1){
return pal;
}
else{
String tmp= "";
tmp = tmp + pal.charAt(pal.length()-1)+isPalindrome(pal.substring(0,pal.length()-1));
return tmp;
}
}
public static void main(String []args){
chkPalindrome hwObj = new chkPalindrome();
String palind = "MADAM";
String retVal= hwObj.isPalindrome(palind);
if(retVal.equals(palind))
System.out.println(palind+" is Palindrome");
else
System.out.println(palind+" is Not Palindrome");
}
}
Ecco un metodo ricorsivo che ignorerà caratteri specificati:
public static boolean isPal(String rest, String ignore) {
int rLen = rest.length();
if (rLen < 2)
return true;
char first = rest.charAt(0)
char last = rest.charAt(rLen-1);
boolean skip = ignore.indexOf(first) != -1 || ignore.indexOf(last) != -1;
return skip || first == last && isPal(rest.substring(1, rLen-1), ignore);
}
Usa in questo modo:
isPal("Madam I'm Adam".toLowerCase(), " ,'");
isPal("A man, a plan, a canal, Panama".toLowerCase(), " ,'");
Non ha senso includere tra maiuscole e minuscole nel metodo ricorsivo dal momento che ha solo bisogno di essere fatto una volta, a meno che non ti è permesso di utilizzare il metodo .toLowerCase().
non c'è alcun codice più piccolo di questo:
public static boolean palindrome(String x){
return (x.charAt(0) == x.charAt(x.length()-1)) &&
(x.length()<4 || palindrome(x.substring(1, x.length()-1)));
}
se si desidera controllare qualcosa:
public static boolean palindrome(String x){
if(x==null || x.length()==0){
throw new IllegalArgumentException("Not a valid string.");
}
return (x.charAt(0) == x.charAt(x.length()-1)) &&
(x.length()<4 || palindrome(x.substring(1, x.length()-1)));
}
LOL B -]
public static boolean isPalindrome(String p)
{
if(p.length() == 0 || p.length() == 1)
// if length =0 OR 1 then it is
return true;
if(p.substring(0,1).equalsIgnoreCase(p.substring(p.length()-1)))
return isPalindrome(p.substring(1, p.length()-1));
return false;
}
Questa soluzione non è case sensitive. Quindi, per esempio, se avete la seguente parola: "adinida", allora si otterrà vero se lo fai "Adninida" o "adninida" o "adinidA", che è quello che vogliamo.
Mi piace risposta @JigarJoshi, ma l'unico problema con il suo approccio è che vi darà false per le parole che contiene le protezioni.
Palindrome esempio:
static boolean isPalindrome(String sentence) {
/*If the length of the string is 0 or 1(no more string to check),
*return true, as the base case. Then compare to see if the first
*and last letters are equal, by cutting off the first and last
*letters each time the function is recursively called.*/
int length = sentence.length();
if (length >= 1)
return true;
else {
char first = Character.toLowerCase(sentence.charAt(0));
char last = Character.toLowerCase(sentence.charAt(length-1));
if (Character.isLetter(first) && Character.isLetter(last)) {
if (first == last) {
String shorter = sentence.substring(1, length-1);
return isPalindrome(shorter);
} else {
return false;
}
} else if (!Character.isLetter(last)) {
String shorter = sentence.substring(0, length-1);
return isPalindrome(shorter);
} else {
String shorter = sentence.substring(1);
return isPalindrome(shorter);
}
}
}
Chiamato da:
System.out.println(r.isPalindrome("Madam, I'm Adam"));
stamperà vero se palindromo, stamperà falso in caso contrario.
Se la lunghezza della stringa è 0 o 1 (non più stringa di controllo), ritorno vero, come il caso base. Questo caso base sarà indicato con funzione di chiamata destra prima di questo. Quindi confrontare per vedere se la prima e l'ultima lettera sono uguali, tagliando le prime e ultime lettere ogni volta che la funzione viene chiamata ricorsivamente.
Ecco il codice per il check-palindromo senza creare molte stringhe
public static boolean isPalindrome(String str){
return isPalindrome(str,0,str.length()-1);
}
public static boolean isPalindrome(String str, int start, int end){
if(start >= end)
return true;
else
return (str.charAt(start) == str.charAt(end)) && isPalindrome(str, start+1, end-1);
}
PlaindromeNumbers public class {
int func1(int n)
{
if(n==1)
return 1;
return n*func1(n-1);
}
static boolean check=false;
int func(int no)
{
String a=""+no;
String reverse = new StringBuffer(a).reverse().toString();
if(a.equals(reverse))
{
if(!a.contains("0"))
{
System.out.println("hey");
check=true;
return Integer.parseInt(a);
}
}
// else
// {
func(no++);
if(check==true)
{
return 0;
}
return 0;
}
public static void main(String[] args) {
// TODO code application logic here
Scanner in=new Scanner(System.in);
System.out.println("Enter testcase");
int testcase=in.nextInt();
while(testcase>0)
{
int a=in.nextInt();
PlaindromeNumbers obj=new PlaindromeNumbers();
System.out.println(obj.func(a));
testcase--;
}
}
}
/**
* Function to check a String is palindrome or not
* @param s input String
* @return true if Palindrome
*/
public boolean checkPalindrome(String s) {
if (s.length() == 1 || s.isEmpty())
return true;
boolean palindrome = checkPalindrome(s.substring(1, s.length() - 1));
return palindrome && s.charAt(0) == s.charAt(s.length() - 1);
}
soluzione semplice 2 Scenario - (Pari o Dispari stringa di lunghezza)
condizione Base & Algo ricorsiva (ch, i, j)
-
i == j // anche len
-
se i
-
altro ritorno ch [i] == ch [j] // condizione base supplementare per i vecchi lunghezza
public class HelloWorld { static boolean ispalindrome(char ch[], int i, int j) { if (i == j) return true; if (i < j) { if (ch[i] != ch[j]) return false; else return ispalindrome(ch, i + 1, j - 1); } if (ch[i] != ch[j]) return false; else return true; } public static void main(String[] args) { System.out.println(ispalindrome("jatin".toCharArray(), 0, 4)); System.out.println(ispalindrome("nitin".toCharArray(), 0, 4)); System.out.println(ispalindrome("jatinn".toCharArray(), 0, 5)); System.out.println(ispalindrome("nittin".toCharArray(), 0, 5)); } }
per voi per raggiungere questo, non solo bisogno di sapere come funziona la ricorsione, ma anche è necessario capire il metodo String. ecco un esempio di codice che ho usato per realizzarla: -
class PalindromeRecursive {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
System.out.println("Enter a string");
String input=sc.next();
System.out.println("is "+ input + "a palindrome : " + isPalindrome(input));
}
public static boolean isPalindrome(String s)
{
int low=0;
int high=s.length()-1;
while(low<high)
{
if(s.charAt(low)!=s.charAt(high))
return false;
isPalindrome(s.substring(low++,high--));
}
return true;
}
}
