Win a copy of The Way of the Web Tester: A Beginner's Guide to Automating Tests this week in the Testing forum!

# Recursive anagram problem

Brandon Peeples
Ranch Hand
Posts: 38
Hi, I'm having trouble getting my anagram method to work. I have to solve it recursively. The explanation of the problem is in the comment section in the beginning of my code. I can't figure out why it reads false for everything I try to test it with. Can anyone help me point out my mistake? Any guidance or advice would be helpful. Thank you.

edited: some code

David Newton
Author
Rancher
Posts: 12617
Before getting into that, you need to make sure that the string method calls you're making are really doing what you think they are.

Brandon Peeples
Ranch Hand
Posts: 38
Ahhhh... I see what you meant. Thanks.

David Newton
Author
Rancher
Posts: 12617
I'm not sure you did :)

Brandon Peeples
Ranch Hand
Posts: 38
I thought I did...? I didn't replace and lower case correctly. I also had an error on "replace2" and on my if(count.........). The code worked correctly when I ran it. What did you mean exactly?

David Newton
Author
Rancher
Posts: 12617
Oh; I thought your edit comment indicated you'd fixed it-the new code looks better :)

Brandon Peeples
Ranch Hand
Posts: 38
Oh, I see what you mean. That was before I fully realized, haha. Thanks again David.

Rob Spoor
Sheriff
Posts: 20708
68
Brandon Peeples wrote:"" + s1.charAt(i);

Please use String.valueOf(s1.charAt(i)) instead. The code you used will use that call in the background, but will also create a StringBuilder:
By using String.valueOf directly you will save that one object. Maybe this is micro-optimization, but using these little API calls is still a good idea.

Just one other question: why do you need your call to be recursive? I can find one way that runs not in O(m * n) with m being the length of the first string and n being the length of the second string*, but in O(k log k) with k being the maximum of m and n. It involves converting the two arrays into character arrays (O(k)), sorting these (O(k log k)), then comparing the two arrays for equality (O(k)). All you will then need is a handful of API calls, most from String, the others from java.util.Arrays. The complete program will run with just 9 method calls, 4 of which are your calls for changing the strings into lower case and removing spaces.

* In your code you loop over m, inside that loop you loop over n.

David Newton
Author
Rancher
Posts: 12617
why do you need your call to be recursive?

I'd assumed it was an assignment.