An anagram is like a mix-up of the letters in a string:
pots is an anagram of stop
Wilma is an anagram of ilWma
I am going through the book Cracking the Coding Interview and in the basic string manipulation there's the problem:
write a method to check if two strings are anagrams of each other.
My method uses StringBuffer
instead of String because you can .deleteCharAt(index)
with StringBuffer/StringBuilder.
public boolean areAnagrams(StringBuffer s1b, StringBuffer s2b) {
for (int i=0; i<s1b.length(); ++i) {
for (int j=0; j<s2b.length(); ++j) {
if (s1b.charAt(i) == s2b.charAt(j)) {
s1b.deleteCharAt(i);
s2b.deleteCharAt(j);
i=0;
j=0;
}
}
}
if (s1b.equals(s2b)) {
return true;
} else
return false;
}
I iterate over every character in s1b and if I find a matching char in s2b I delete them both from each string and restart the loop (set i
and j
to zero) because the length of the StringBuffer
objects changes when you .deleteCharAt(index)
.
I have two questions:
- Should I use
StringBuilder
overStringBuffer
(in Java)? - How can I make this faster?
In regards to fasterness:
This method is good in that it doesn't require any additional space, but it sorta destroys the data as you're working on it. Are there any alternatives that I have overlooked that could potentially preserve the strings but still see if they are anagrams without using too much external storage (i.e. copies of the strings are not allowed -- as a challenge)?
And, if you can use any sort of storage space in addition to this, can one lower the time complexity to \$O(n)\$ (technically \$O(2n)\$) instead of \$O(n^2)\$?
Also, the above code might not compile because I just wrote it from scratch in here; sorry if it's bugg'd.
StringBuilder
because it doesn't use synchronization here. It will be faster and you aren't using multiple threads to access the same buffer, makingStringBuffer
slower with no payoff. As for your code, no need to reseti
since you don't want to start over, and ifi
gets to the end of the first string they aren't anagrams. \$\endgroup\$