1
\$\begingroup\$
  private String sort(String word) {
    char[] content = word.toCharArray();
    Arrays.sort(content);
    return new String(content);
  }

  private boolean isPermutation(String s1, String s2) {
    s2 = s2.toLowerCase();
    if (s1.length() != s2.length()) {
      return false;
    }
    if (s1.equals(s2)) {
      return true;
    }
    return sort(s1).equals(sort(s2));
  }

Could the above solution can be optimized(in space and time)?
I think the worst case running time would be: \$O(nlog)\$

\$\endgroup\$
  • \$\begingroup\$ Please delete the call to toLowerCase, since it has nothing to do with permutations. \$\endgroup\$ – Roland Illig Oct 8 '16 at 10:29
2
\$\begingroup\$

For short strings, this algorithm and the implementation is good.

If your strings are longer than a few 100 characters and if they only contain ASCII characters, it may be more efficient to count how many times each character appears and then compare if all these counts are equal. This algorithm has complexity \$O(n)\$, but the (invisible) constant factor is larger.

If your strings contain arbitrary Unicode code points, using a simple array for the counts becomes impractical, since that array needs to have 0x11_0000 entries. Looping over these entries and comparing them is \$O(1)\$, but nevertheless it is slow.

Therefore, for practical purposes and the general case, your code looks perfect. There might be some improvements if you know more about the string's contents, but these are on the implementation level, not on the algorithm complexity level.

\$\endgroup\$
  • \$\begingroup\$ Yet another approach might be to substitute each occurrence of a character by a unique prime number, then multiply all numbers of a string. Permutations of a String will have the same result. This has other problems like possibly creating very large numbers and the substitution of characters with primes. But it avoids explicitly counting the occurrences of each character. \$\endgroup\$ – I'll add comments tomorrow Oct 8 '16 at 11:28
  • \$\begingroup\$ Since sorting is involved therefore we have O(nlogn), I am missing something? \$\endgroup\$ – CodeYogi Oct 8 '16 at 11:44
  • \$\begingroup\$ @I'lladdcommentstomorrow That technique only really makes sense for small words; multiplication on big integers is slow and space inefficient. \$\endgroup\$ – Veedrac Oct 8 '16 at 11:53
  • \$\begingroup\$ @RolandIllig If dealing with arbitrary code points, just use a HashMap instead of an array. It's still asymptotically faster than sorting. \$\endgroup\$ – Veedrac Oct 8 '16 at 11:55
  • \$\begingroup\$ @Veedrac asymptotically you may be right. I'm more concerned about practical performance though, therefore preferring \$O(n \log n)\$ with a small constant over \$O(n)\$ with a large constant. Using a HashMap looks like using a lot of heap memory during the computation. \$\endgroup\$ – Roland Illig Oct 8 '16 at 18:45
1
\$\begingroup\$

Here's what we have so far:

  • Sorting using a general sort algorithm will be O(NlogN) on average where N is the number of characters.

  • Sorting using a counting sort will be O(N), but will require O(A) space, where A is the "size" of the alphabet, and O(A) startup cost.

There is an approach which will you O(N) time in the best and average cases1, in the worst case O(NlogN), and no memory usage / startup.

All you need is to design a hashing algorithm that is sensitive to the characters in the string, but insensitive to their position. A really simple one would be so sum or take the product of the character codes, using int or long arithmetic. Then the algorithm is this:

boolean isPermuntation(String a, String b) {
   if (hash(a) != hash(b)) {
      return false;
   } else {
      return sorted(chars(a)).equals(sorted(chars(b));
   }
}

The worst cases occur what a and b are permutations, or when they are not but the hashes turn out to be the same.


1 - On average ... for strings chosen at random from the set of all strings less than a certain length.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.