Re: IsAnagram

Martin wrote:

I am looking for the best algorithm to check if two words are
anagrams. Here the signature of the method :

bool IsAnagram(char[] wordOne, char[] wordTwo)

Here are the strategies I am thinking of :
- Brute-Force (One loop inside the other one) O(n^2)
- Sort both words and compare both arrays. O(n^2) considering that I
use BubbleSort and words are both short (less than 30 characters).
- Find a way to create a signature for each word (e.g. A = 1, B = 2,
etc.) However, I can have a problem here... The sum for both words
can be the same with different letters.

So I am looking for the most efficient algorithm. Do you have an idea?

Sort both sounds like the most efficient. You should probably use
a simple sort such as shell sort, which is much faster than bubble,
and is better than O(N*N). If one argument comes from a table then
it can be stored in sorted order.

Bear in mind that you are not passing arrays, you are passing
pointers to the first item in the array. So you need to copy the
array first. Assuming they are strings (zero terminated) you will
find the lengths in the process.

--
<http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
<http://www.securityfocus.com/columnists/423>
<http://www.aaxnet.com/editor/edit043.html>
<http://kadaitcha.cx/vista/dogsbreakfast/index.html>
cbfalconer at maineline dot net


--
Posted via a free Usenet account from http://www.teranews.com

.

Relevant Pages

  • Re: String comparision efficency
    ... The algorithm for sorthas to be stable (specified in the ... class-level docs for Arrays), which makes the order resulting from ... Using a stable sort makes a reasonably good sense anyway. ...
    (comp.lang.java.programmer)
  • Re: Multiple Arrays Sorting
    ... >each array will be surrounded by arrays having the closest ... Therefore, ISTM, a "sorting" algorithm may get ... sort that list of indexes; if essential, ...
    (borland.public.delphi.language.objectpascal)
  • Re: What is the most fast sorting algorithm?
    ... What is the most fast sorting algorithm?) ... core Osort. ... If you only use the Osort without the "clean-up" ... some arrays won't get properly sorted. ...
    (comp.programming)
  • Re: "Sorting" assignment
    ... algorithm such as tbe bubble sort should be given a free pass because ... I would tailor which algorithm to start with by how the student thinks ... If you only learn the beautiful side of programming, ...
    (comp.programming)
  • Re: puzzle
    ... >> Christopher Barber wrote: ... >> or understanding among programming professionals. ... > algorithm "close to" O. ... bubble sort, it is almost always acceptable to use an interchange sort: ...
    (comp.programming)