353 - Pesky Palindromes

[brianfry713]

My AC code reads a string at a time, not line by line. The input "boy ", with a trailing space (not including the quotes), would be converted to "boy" with no trailing space in my code.

[Yousuf]

Code: Select all

AC.. :D 

[brianfry713]

The string 'gzdvljcpxpepn' contains 13 palindromes.

[Yousuf]

Thanks " brianfry713" I get AC now. Thanks for help.

[mirak]

Code: Select all

import java.io.*;
import java.util.Formatter;
import java.util.Scanner;

public class Training {
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		String output = "";
		while (input.hasNext("0")==false) {
			String s = input.next();
			int num = 0;
			char[] a = new char[s.length()];
			for (int i = 0; i < a.length; i++) {
				a[i] = s.charAt(i);
			}
			char[] b = new char[a.length];
			int k = 0;
			for (int i = 0; i < a.length; i++) {
				if (i == 0) {
					b[k] = a[i];
					k++;
				} else {
					boolean isTrue = numC(b, k, a[i]);
					if (isTrue == true) {
						b[k] = a[i];
						k++;
					}
				}
			}
			for (int i = 0; i <= s.length(); i++) {
				for (int j = i + 1; j <= s.length(); j++) {
					String u = s.substring(i, j);
					if (u.length() != 1) {
						if (isPalindrome(u, 0, u.length() - 1) == true) {
							num++;
						}
					}
				}
			}
			output+="The string "+"'"+s+"' contains "+(num+k)+" palindromes.\n";
		}
		output=output.trim();
		System.out.println(output);
	}

	public static boolean isPalindrome(String s, int i, int j) {
		if (i == j || i > j) {
			return true;
		} else {
			if (s.charAt(i) == s.charAt(j)) {
				return isPalindrome(s, i + 1, j - 1);
			} else {
				return false;
			}
		}
	}

	public static boolean numC(char[] ar, int j, char a) {
		int num = 0;
		for (int i = 0; i < j; i++) {
			if (ar[i] == a) {
				num++;
			}
		}
		if (num > 0) {
			return false;
		} else {
			return true;
		}
	}

}

i don't know why am gettin' WA here .. if someone can help ...

[brianfry713]

Use class Main
http://uva.onlinejudge.org/index.php?op ... &Itemid=30

[alimbubt]

Input:

Code: Select all

alim
bubt
illusion
acmicpc
worldfinal
mirpur
abdulalim
alimbubt
cseuuu
aaaaaaa
bbbbbbb
aaaaaaaaaammmmmmmmmmmmmmmaaaaaaaaaa
sssssssguggudfgighi
djsfdsgfjggjsdfjgdsjkg
iuwetrewuuuuuiweughsalfujgkf
iutwrigmdlbbckbj
newkeyboard
dffdg

Output:

Code: Select all

The string 'alim' contains 4 palindromes.
The string 'bubt' contains 4 palindromes.
The string 'illusion' contains 7 palindromes.
The string 'acmicpc' contains 6 palindromes.
The string 'worldfinal' contains 9 palindromes.
The string 'mirpur' contains 5 palindromes.
The string 'abdulalim' contains 8 palindromes.
The string 'alimbubt' contains 8 palindromes.
The string 'cseuuu' contains 6 palindromes.
The string 'aaaaaaa' contains 7 palindromes.
The string 'bbbbbbb' contains 7 palindromes.
The string 'aaaaaaaaaammmmmmmmmmmmmmmaaaaaaaaaa' contains 35 palindromes.
The string 'sssssssguggudfgighi' contains 17 palindromes.
The string 'djsfdsgfjggjsdfjgdsjkg' contains 8 palindromes.
The string 'iuwetrewuuuuuiweughsalfujgkf' contains 18 palindromes.
The string 'iutwrigmdlbbckbj' contains 14 palindromes.
The string 'newkeyboard' contains 10 palindromes.
The string 'dffdg' contains 5 palindromes.

[farhan36]

i am getting WA for this problem. please help.

Code: Select all

#include<iostream>
#include<cstdio>
#include<new>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<fstream>
#include<algorithm>
#include<functional>
#include<vector>
#include<list>
#include<deque>

using namespace std;

int main()
{
    string s;
    int count=0;
    bool flag = false,matched = false;
    while(getline(cin,s))
    {

        char ch[26]="\0";
        count =0;
        flag = false;
        matched = false;
        for(int i=0;i<s.length();i++)
        {
            if(count>0)
            {
                for(int j=0;j<count;j++)
                {
                    if(s[i]==ch[j])
                    {
                        flag = true;
                        break;
                    }
                }
                if(!flag) ch[count++] = s[i];
                flag = false;
            }

            else ch[count++] =s[i];
        }

        for(int i=0;i<s.length()-1;i++)
        {
            for(int j=s.length()-1;j>=i+1;j--)
            {
                int k=i;
                int l =j;
                int c=i;
                while(c<=(k+l)/2)
                {
                    if(s[k]!=s[l])
                    {
                        matched = true;
                        break;
                    }
                    k++;
                    l--;
                    c++;

                }
                if(!matched)
                {
                    count++;

                }
                matched = false;
            }
        }

        cout << "The string '" << s << "' contains " << count <<" palindromes.\n";
    }

}

[brianfry713]

Try the I/O in the post before yours.

[uDebug]

My code passed all the test cases mentioned in this thread but I was still get a WA. So, I thought of this some more and came up with the following input - on which my code didn't match the expected output. This way, I was able to troubleshoot my issue and get a AC. I'm sharing the test cases which helped me identify the bug in my code and the AC output.

Input:

Code: Select all

zzcatzztaczz
zzcatzzcatzzcat

AC Output:

Code: Select all

The string 'zzcatzztaczz' contains 10 palindromes.
The string 'zzcatzzcatzzcat' contains 5 palindromes.

Also note that since the problem clearly states "For each non-empty input line..." it's clear that there are no blank lines that need to be worried about as part of the input.

[solve14]

Getting Runtime Error, don't have a clue, help is appreciated
Also suggestion on how to improve the all substring generator code part is appreciated.

Code: Select all

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 class Palindrome {

   public int checkPalindrome(String str)
   {
       String newStr="";
       
       for(int i=str.length()-1;i>=0;i--)
       {
          newStr+=str.charAt(i);
       }
       
       if(str.equals(newStr))
       {
           return 1;
       }
       else
       {
           return 0;
       }
   }

    public static void main(String[] args)throws IOException {
        
      
       InputStreamReader isr = new InputStreamReader(System.in);
       BufferedReader br = new BufferedReader(isr);
       ArrayList<String>al=new ArrayList<String>(); 
       String sub,usrStr;
       int palindrome=0;
       Palindrome p=new Palindrome();
       
       while((usrStr=br.readLine())!=null)
       {
 //substring generator
           for(int i=0;i<usrStr.length();i++)
           {
               for(int j=1;j<=usrStr.length()-i;j++)
               {
                    sub = usrStr.substring(i, i+j);
                     al.add(sub);
                    
               }  
           }
           
           HashSet hs = new HashSet();
           hs.addAll(al);                            //will add the unique substrings
           al.clear();
           al.addAll(hs);
           
           for(int m=0;m<al.size();m++)
           {
               String checkStr=al.get(m);
                if(p.checkPalindrome(checkStr)==1)
                     {
                           palindrome++;
                     }
           }
           
           System.out.println("The string '"+usrStr+"' contains "+palindrome+" palindromes.");
           palindrome=0;
           al.clear();
       }

    }
}

[brianfry713]

Use class Main

[sampad74]

i got Wa.in my code i noticed that this if condition is not working properly.bt i don't know why??there may be some other mistakes.please help me..here is my code.

Code: Select all

#include<string.h>
#include<stdio.h>
char a[90];
int t;
int is(void)
{
    int i,g=0;
    for(i=0;i<(t/2);i++)
    {
        if(a[i]==a[t-i-1])
        {
            g++;
        }
        else break;
    }
    if(g==(t/2)) return 1;
    else return 0;
}
int main(void)
{
char s[180][90];
    while(gets(a))
    {

    t=strlen(a);
    //printf("t=%d\n",t);
    int i,j,k,c=0,l;
    if(is()==1)
    {
      //  printf("pelindrome\n");
        c=t/2;
    }
    else
    {
        int m1=0,n1;
    for(int i=0;i<t-1;i++)
    {
        for(j=1;j<t;j++)
        {
            int f=6;
                if(a[i]==a[j])
                {
                    n1=0;
                    s[m1][n1]=a[i];
                    f=0;
                    l=j-1;
                    for(k=i+1;k!=j;k++,l--)
                    {

                        if(a[k]!=a[l])
                        {
                            f=1;
                            //m1--;
                            break;
                        }
                        else
                        {
                            n1++;
                            s[m1][n1]=a[k];
                        }
                    }
                }
                if(f==0)
                {
                    int il;
                    for(il=0;il<m1;il++)
                    {
                        //printf("peli %s\n",s[m1]);
                        if(!strcmp(s[m1],s[il]))
                        {
                            //not working !!!!

                            //printf("m1 %d c %d il %d\n",m1,c,il);
                            f=1;
                        }
                    }
                    if(f==0)
                    {
                        m1++;
                        c++;
                    }
                }
        }
    }
    }
   //printf("uniq pelin %d\n",c);
    //if(t>0) c++;
    int v;
    for(i=0;i<t;i++)
    {
        v=1;
        for(j=i-1;j>=0;j--)
        {
            if(a[i]==a[j])
            {
                v=0;
                break;
            }
        }
        if(v==1) c++;
    }
    printf("The string '%s' contains %d palindromes.\n",a,c);

    }
    return 0;
}

[brianfry713]

Try using scanf("%s") instead of gets.
The string 'aaa' contains 3 palindromes.