java - Compare strings using recursion -
i've got homework assignment can't figure out. have write static method match(string x, string y) returns boolean whether or not string x , string y match. matching process should allow "wild cards" such '@' character match single character , '*' character match 0 or more characters of type. i'm not allowed use loops , have use recursion. i've written far this...
public class comparestrings { public static boolean match(string x, string y) { if (x.length() <= 1 && y.length() <= 1) { if (x.equals("*") || y.equals("*")) { return true; } if ((x.length() == 1 && y.length() == 1) && (x.equals("@") || y.equals("@"))) { return true; } return x.equals(y); } string x1 = ""; string x2 = ""; string y1 = ""; string y2 = ""; if (x.length() == 0 && y.charat(0) == '*') { y2 = y.substring(1, y.length()); } if (y.length() == 0 && x.charat(0) == '*') { x2 = x.substring(1, x.length()); } if (x.length() > 1 && y.length() > 1) { if (x.length() != y.length() && !x.contains("*") && !y.contains("*")) { return false; } if (x.charat(0) == '*') { x1 = "*"; x2 = x.substring(1, x.length()); y1 = "*"; y2 = y.substring(y.length()-x2.length(), y.length()); } else if (y.charat(0) == '*') { y1 = "*"; y2 = y.substring(1, y.length()); x1 = "*"; x2 = x.substring(x.length()-y2.length(), x.length()); } else { x1 = x.substring(0, 1); x2 = x.substring(1, x.length()); y1 = y.substring(0, 1); y2 = y.substring(1, y.length()); } } return match(x1, y1) && match(x2, y2); } public static void main(string[] args) { system.out.println(match("hello", "hello.") + " 1 false"); // should return false system.out.println(match("hello", "jello") + " 2 false"); // should return false system.out.println(match("hello", "h@llo") + " 3 true"); // should return true system.out.println(match("hello", "h@@@@") + " 4 true"); // should return true system.out.println(match("hello", "h*") + " 5 true"); // should return true system.out.println(match("hello", "*l*") + " 6 true"); // should return true system.out.println(match("anystring", "*") + " 7 true"); // should return true system.out.println(match("help", "h@@@@") + " 8 false"); // should return false system.out.println(match("help", "h*") + " 9 true"); // should return true system.out.println(match("help", "*l*") + " 10 true"); // should return true system.out.println(match("help", "*l*p") + " 11 true"); // should return true system.out.println(match("help", "h@llo") + " 12 false"); // should return false system.out.println(match("", "*") + " 13 true"); // should return true system.out.println(match("", "***") + " 14 true"); // should return true system.out.println(match("", "@") + " 15 false"); // should return false system.out.println(match("", "") + " 16 true"); // should return true } }
the main method test program given assignment. realize code little messy - scrambling bit - can seem of working. example doesn't return right value number 11. false when should true. reason think happening because since string y starts '', thing method splits both x , y strings last 3 characters, though first '' in y supposed represent 2 characters. how can make cases return match?
basically need understand concept of recursion (that objective of homework). way recursion works everytime function calls itself, current execution (variables/ execution info) goes onto stack , sleeps there till new call finishes.
to solve problem have mentioned, lets take simple example, hello , h@llo. basic way solve problem match service call again , again till
a perfect match found - return true
a failure condition found- return false
in absence of above 2, match calls 1 character less prev call
something like
call 1: hello & h@llo// calls match again , present call moves stack, waits reply
call 2: ello & @llo //matches special character
call 3: llo , llo// perfect match return true call 2
back call 2: receives true prv call , returns call 1
back call 1: receives true , returns main.
once understand concept of recursion stack, solving problem simple
your final match method
public static boolean match(string x, string y) { //if both empty if(x.length()==0 && y.length()==0) return true; //if 1 empty if(x.length()==0 ) { if(y.charat(0)!='*') return false; if(y.length()!=1) //border line case return match(x,y.substring(1)); else return true; } if(y.length()==0 ) { if(x.charat(0)!='*') return false; if(x.length()!=1) //border line case return match(y,x.substring(1)); else return true; } //base case if(x.equals(y) || x.equals("*") || y.equals("*")) { return true;//we done strings equal } //we here means strings not equal yet if(x.charat(0)=='@' || y.charat(0)=='@' ||x.charat(0)==y.charat(0)) { if(x.length()==1 && y.length()==1) return true;//this last character if(x.length()>1 && y.length()>1) { //we have single char wild card or char 0 equal, lets remove char @ 0th location , check again return (match(x.substring(1),y.substring(1))); } } if(x.charat(0)=='*') { //this interesting now, need skip 0..n number of characters till find matching pattern //case 0 chars: he*llo , hello if(match(x.substring(1),y)==true) { return true; } else if (match(x.substring(1),y.substring(1))==true) { //case 1: he*lo , hello return true; } else { //case n chars: h*o , hello return (match(x, y.substring(1))); } } if(y.charat(0)=='*') { //this interesting now, need skip 0..n number of characters till find matching pattern //case 0 chars: he*llo , hello if(match(y.substring(1),x)==true) { return true; } else if (match(x.substring(1),y.substring(1))==true) { //case 1: he*lo , hello return true; } else { //case n chars: h*o , hello return (match(y, x.substring(1))); } } //nothing worked out return false; }
Comments
Post a Comment