Recursive anagram problem

[Brandon Peeples]

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.

    
	/**
	 * Returns true if s1 and s2 represent phrases that are anagrams 
	 * of each other. Anagram phrases are strings that contain the same 
	 * letters in the same multiplicities (counts). You should perform a 
	 * case-insensitive comparison, ignoring differences in capitalization 
	 * between s1 and s2; for example, "Acres" and "CARES" should be 
	 * considered anagrams. You should also ignore spaces;
	 */
	public boolean phraseAnagramCheck(String s1, String s2) {
		int count = 0;
		s1.toLowerCase();
		s2.toLowerCase();
		s1.replaceAll(" ","");
		s2.replaceAll(" ","");
		if(count == s1.length() && count == s2.length()) {
			return true;
		}
		for(int i=0; i<s1.length(); i++) {
			for(int j=0; j<s2.length(); j++) {
				if(s1.charAt(i) == s2.charAt(j)) {
					String replace1 = "" + s1.charAt(i);
					String replace2 = "" + s2.charAt(j);
					count++;
					s1 = s1.replaceFirst(replace1, "");
					s2 = s2.replaceFirst(replace2, "");
					return phraseAnagramCheck(s1, s2);
				} 
			}
		}
		return false;
	}

edited: some code

[David Newton]

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]

Ahhhh... I see what you meant. Thanks.

[David Newton]

I'm not sure you did :)

[Brandon Peeples]

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?

 

	public boolean phraseAnagramCheck(String s1, String s2) {
		int count = 0;
		s1 = s1.toLowerCase();
		s2 = s2.toLowerCase();
		s1 = s1.replaceAll(" ","");
		s2 = s2.replaceAll(" ","");
		if(count == s1.length() && count == s2.length()) {
			return true;
		}
		for(int i=0; i<s1.length(); i++) {
			for(int j=0; j<s2.length(); j++) {
				if(s1.charAt(i) == s2.charAt(j)) {
					String replace1 = "" + s1.charAt(i);
					String replace2 = "" + s2.charAt(j);
					count++;
					s1 = s1.replaceFirst(replace1, "");
					s2 = s2.replaceFirst(replace2, "");
					return phraseAnagramCheck(s1, s2);
				} 
			}
		}
		return false;
	}
 

[David Newton]

Oh; I thought your edit comment indicated you'd fixed it-the new code looks better :)

[Brandon Peeples]

Oh, I see what you mean. That was before I fully realized, haha. Thanks again David.

[Rob Spoor]

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:

new StringBuilder().append("").append(s1.charAt(i)).toString();

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]

why do you need your call to be recursive?

I'd assumed it was an assignment.