Results 1 to 6 of 6
  1. #1
    i4ba1 is offline Member
    Join Date
    Aug 2008
    Posts
    13
    Rep Power
    0

    Question How to count number of palindrome in a string??

    Hai all i have a problem in palindrome. this is the question:
    Create a function findPalin() that takes a string of characters as an argument and returns the number of palindromes (a string in which the sequence of characters is the same forwards and backwards) in that string. There is no special character. This function should be as fast as possible.

    Ex:

    "aa" returns 1
    "aabb" returns 2
    "222" returns 3
    "baaab3" returns 4

    How is the algorithm to solve this problem?. anyone can helo me, please?.

  2. #2
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,662
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by i4ba1 View Post
    Hai all i have a problem in palindrome. this is the question:
    Create a function findPalin() that takes a string of characters as an argument and returns the number of palindromes (a string in which the sequence of characters is the same forwards and backwards) in that string. There is no special character. This function should be as fast as possible.

    Ex:

    "aa" returns 1
    "aabb" returns 2
    "222" returns 3
    "baaab3" returns 4

    How is the algorithm to solve this problem?. anyone can helo me, please?.
    Do you want to count 'sub palindromes' as palindromes as well? i.e. "abbaabba" contains how many palindromes? If so you have to check every substring starting at position i and ending at position j (exclusive) and see if it is a palindrome or not. The loop looks like this:

    Java Code:
    for (int i= 0; i < string.length()-2; i++)
       for (int j= i+2; i < string.length(); j++)
          // check substring at position [i, j)
    The is a O(n^2) algorithm and I doubt if it can be done any better ...

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    i4ba1 is offline Member
    Join Date
    Aug 2008
    Posts
    13
    Rep Power
    0

    Question

    This is my code for palindrome:
    Java Code:
    private int countPalin(String str)
    	{
    		int numPalin = 0;
    		for (int i = 2; i <= str.length(); i++) 
    		{
    			for (int j = 0; j+i <= str.length(); j++) 
    			{
    				System.out.println("j "+j);
    				System.out.println("i "+i);
    				String test = str.substring(j, i);
    				
    				if (checkPalin(test) && !test.equals("")) 
    				{
    					System.out.println("test "+test);
    					numPalin++;
    				}
    			}
    		}
    		
    		return numPalin;
    	}
    	
    	private boolean checkPalin(String str)
    	{
    		StringBuffer sb = new StringBuffer(str);
    		String rev = sb.reverse().toString();
    		
    		//System.out.println("str "+str);
    		//System.out.println("rev "+rev);
    		if (!str.equalsIgnoreCase(rev)) 
    		{
    			return false;
    		}
    		
    		return true;
    	}
    this code run for word "aa","aabb","222" but with word "baaab3" the error String index out of bounds sho. any one can help me to solve this problem?.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,662
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by i4ba1 View Post
    This is my code for palindrome:
    Java Code:
    private int countPalin(String str)
    	{
    		int numPalin = 0;
    		for (int i = 2; i <= str.length(); i++) 
    		{
    			for (int j = 0; j+i <= str.length(); j++) 
    			{
    				System.out.println("j "+j);
    				System.out.println("i "+i);
    				String test = str.substring(j, i);
    				
    				if (checkPalin(test) && !test.equals("")) 
    				{
    					System.out.println("test "+test);
    					numPalin++;
    				}
    			}
    		}
    		
    		return numPalin;
    	}
    	
    	private boolean checkPalin(String str)
    	{
    		StringBuffer sb = new StringBuffer(str);
    		String rev = sb.reverse().toString();
    		
    		//System.out.println("str "+str);
    		//System.out.println("rev "+rev);
    		if (!str.equalsIgnoreCase(rev)) 
    		{
    			return false;
    		}
    		
    		return true;
    	}
    this code run for word "aa","aabb","222" but with word "baaab3" the error String index out of bounds sho. any one can help me to solve this problem?.
    Your first two loop bounds are incorrect; they should be:

    Java Code:
    for (int i= 0; i < s.length()-2; i++)
       for (int j= i+2; j <= s.length(); j++)
          ...
    These loops iterate over all pairs (i, j), i < j <= s.length() where s.substring(i, j) has to be checked for the palindrome property. Note that i+2 <= j which takes care that no trivial palindromes are checked.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    i4ba1 is offline Member
    Join Date
    Aug 2008
    Posts
    13
    Rep Power
    0

    Question

    Thank you JosAh it's working. i try your loop, but why the first loop must str.length() -2?, if i try without str.length() -2 it's working to.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,662
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by i4ba1 View Post
    Thank you JosAh it's working. i try your loop, but why the first loop must str.length() -2?, if i try without str.length() -2 it's working to.
    You only want to test possible palindromes with a length of at least 2; smaller palindromes, e.g. "a" are trivial and you don't want to count them.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

Similar Threads

  1. how to count number of pages printed?
    By absmarty in forum New To Java
    Replies: 10
    Last Post: 01-31-2012, 06:20 PM
  2. day number count
    By droidus in forum New To Java
    Replies: 14
    Last Post: 03-23-2011, 10:15 PM
  3. Count number of digits in string using scanner
    By wendysbiggy in forum New To Java
    Replies: 35
    Last Post: 01-20-2010, 05:11 AM
  4. Array count number Occurances
    By gwithey in forum New To Java
    Replies: 2
    Last Post: 04-17-2009, 08:34 PM
  5. Replies: 8
    Last Post: 02-04-2009, 08:55 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •