By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,648 Members | 1,528 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,648 IT Pros & Developers. It's quick & easy.

How can i get the following result using only recursion

P: 5
Expand|Select|Wrap|Line Numbers
  1. public static void main(String args[]) { 
  2.  System.out.println(match("hello", "hello.")); // should return false
  3.  System.out.println(match("hello", "jello")); // should return false
  4.  System.out.println(match("hello", "h@llo")); // should return true
  5.  System.out.println(match("hello", "h@@@@")); // should return true
  6.  System.out.println(match("hello", "h*")); // should return true
  7.  System.out.println(match("hello", "*l*")); // should return true
  8.  System.out.println(match("anyString", "*")); // should return true
  9.  System.out.println(match("help", "h@@@@")); // should return false
  10.  System.out.println(match("help", "h*")); // should return true
  11.  System.out.println(match("help", "*l*")); // should return true
  12.  System.out.println(match("help", "*l*p")); // should return true
  13.  System.out.println(match("help", "h@llo")); // should return false
  14.  System.out.println(match("", "*")); // should return true
  15.  System.out.println(match("", "***")); // should return true
  16.  System.out.println(match("", "@")); // should return false
  17.  }
Mar 31 '13 #1
Share this Question
Share on Google+
9 Replies


Rabbit
Expert Mod 10K+
P: 12,421
Please use code tags when posting code.

I don't see what your code has to do with recursion.
Mar 31 '13 #2

P: 5
This is what I did but it doesnt seem to work keep getting false for all of them.
Expand|Select|Wrap|Line Numbers
  1. public class CompareStrings { 
  2. public static boolean match(String x, String y, boolean wildCard ) {
  3.     //Both strings are empty
  4.     if((x.length() == 0) &&(y.length()==0))
  5.         {
  6.             return true;
  7.         }
  8.     //Second string is empty and there is wildCard character
  9.     if(y.length() == 0 && wildCard)
  10.         {
  11.             return true;
  12.         }
  13.     if(x.length() == 0 && y.length() > 0 && y.charAt(0) == '*')
  14.     {
  15.         String newY = y.replace('0','1');
  16.         return match(x, newY, true);
  17.     }
  18.     //one string is empty, and the second one is not
  19.     if(x.length()* y.length()== 0)
  20.     {
  21.         return false;
  22.     }
  23.     if(wildCard)
  24.     {
  25.         String newX = x.replace('0','1');
  26.         if(match(newX,y,true) || match(newX,y, false))
  27.         {
  28.             return true;
  29.         }
  30.     }
  31.     else{
  32.         if(y.charAt(0) == '*')
  33.         {
  34.             String newY = y.replace('0','1');
  35.             if(match(x,newY,true)|| match(x,newY,false))
  36.             {
  37.                 return true;
  38.             }
  39.         }
  40.         else{
  41.             if(x.charAt(0) == y.charAt(0))
  42.             {
  43.                 String newX = x.replace('0','1');
  44.                 String newY = y.replace('0','1');
  45.                 return match(newX, newY, false);
  46.             }
  47.             else{
  48.                 return false;
  49.             }
  50.         }
  51.     }
  52.     return false;    
  53. }
  54.  
  55. public static void main(String args[]) { 
  56.  System.out.println(match("hello", "hello.")); // should return false
  57.  System.out.println(match("hello", "jello")); // should return false
  58.  System.out.println(match("hello", "h@llo")); // should return true
  59.  System.out.println(match("hello", "h@@@@")); // should return true
  60.  System.out.println(match("hello", "h*")); // should return true
  61.  System.out.println(match("hello", "*l*")); // should return true
  62.  System.out.println(match("anyString", "*")); // should return true
  63.  System.out.println(match("help", "h@@@@")); // should return false
  64.  System.out.println(match("help", "h*")); // should return true
  65.  System.out.println(match("help", "*l*")); // should return true
  66.  System.out.println(match("help", "*l*p")); // should return true
  67.  System.out.println(match("help", "h@llo")); // should return false
  68.  System.out.println(match("", "*")); // should return true
  69.  System.out.println(match("", "***")); // should return true
  70.  System.out.println(match("", "@")); // should return false
  71.  } 
Mar 31 '13 #3

P: 5
I want to compare the string using recursion also a wild card for example The matching process should allow "wild cards". A '@' character will match with any other single character and a '*' character will match with 0 or more characters of any type.
Mar 31 '13 #4

Rabbit
Expert Mod 10K+
P: 12,421
Why use recursion when iteration is simpler?
Mar 31 '13 #5

10K+
P: 13,264
Why are you replacing 0 with 1 in the Strings? For a recursive compare you need to add an index to your function. Then you run through the strings comparing positions 0 to N in the strings while comparing stringX.charAt(index) and stringY.charAt(index).
Mar 31 '13 #6

P: 5
I need to know how to do it with recursion for a test,:(
Mar 31 '13 #7

10K+
P: 13,264
Start with a normal compare using the method I mentioned above, then when you get it working add the wildcards feature.
Mar 31 '13 #8

P: 5
I did this but kept getting un correct result can someone help me fix it up?

Expand|Select|Wrap|Line Numbers
  1. public class CompareStrings { 
  2. public static boolean match(String x, String y) {
  3.     return match(x.toCharArray(), y.toCharArray(), x.length() - 1, y.length() - 1);
  4. }
  5.  
  6. private static boolean match(char[] x, char[] y, int xPosition, int yPosition) {
  7.     if (xPosition < 0 || yPosition < 0) {
  8.         return false;
  9.     }
  10.     if (xPosition == 0 && yPosition == 0) {
  11.         return true;
  12.     }
  13.     if (x[xPosition] == y[yPosition] || x[xPosition] == '@') {
  14.         return match(x, y, xPosition - 1, yPosition - 1);
  15.     }
  16.     if (x[xPosition] == '*') {
  17.         if (x[xPosition - 1] == '@') {
  18.             /* @* => @ matter of taste. Sure there are counter examples. */
  19.             return match(x, y, xPosition - 2, yPosition - 1);
  20.         }
  21.         final int newYPosition = String.valueOf(y).lastIndexOf(x[xPosition - 1]);
  22.         if (newYPosition >= 0) {
  23.             return match(x, y, xPosition - 1, newYPosition);
  24.         }
  25.     }
  26.     return false;
  27. }
  28.  
  29. public static void main(String args[]) { 
  30.  System.out.println(match("hello", "hello.")); // should return false
  31.  System.out.println(match("hello", "jello")); // should return false
  32.  System.out.println(match("hello", "h@llo")); // should return true
  33.  System.out.println(match("hello", "h@@@@")); // should return true
  34.  System.out.println(match("hello", "h*")); // should return true
  35.  System.out.println(match("hello", "*l*")); // should return true
  36.  System.out.println(match("anyString", "*")); // should return true
  37.  System.out.println(match("help", "h@@@@")); // should return false
  38.  System.out.println(match("help", "h*")); // should return true
  39.  System.out.println(match("help", "*l*")); // should return true
  40.  System.out.println(match("help", "*l*p")); // should return true
  41.  System.out.println(match("help", "h@llo")); // should return false
  42.  System.out.println(match("", "*")); // should return true
  43.  System.out.println(match("", "***")); // should return true
  44.  System.out.println(match("", "@")); // should return false
  45.  } 
Mar 31 '13 #9

10K+
P: 13,264
You should try to find out what's wrong with the code by putting printlns to see the values of variables. Also, you need to think about the logic first before writing anything on the compiler. I don't see why you are putting x and y positions at this stage. First, get a basic recursive compare to work, it only needs to take the two strings and the current position we are comparing at. You call it with zero the first time and move up through the strings comparing characters at the same locations.
Mar 31 '13 #10

Post your reply

Sign in to post your reply or Sign up for a free account.