How to compare anagrams without toCharArray method?

/*
 * 
 * 
 */

import java.util.Scanner;
import java.util.Arrays;


public class Anagram
{
  public static void main(String[] args)
  {

Scanner sc = new Scanner(System.in);
String one, two;

System.out.print("Enter first sentence: ");
String s1 = sc.nextLine();
System.out.print("Enter second sentence: ");
String s2 = sc.nextLine();

sc.close();

s1 = s1.toLowerCase();
char[] chars = s1.toCharArray();
Arrays.sort(chars);
String 开发者_C百科sort1 = new String(chars);
System.out.println(sort1 + " are the letters of " + s1 + " in order");

s2 = s2.toLowerCase();
char[] chars2 = s2.toCharArray();
Arrays.sort(chars2);
String sort2 = new String(chars2);
System.out.println(sort2 + " are the letters of " + s2 + " in order");

if(sort1.equals(sort2))
  System.out.println(s1 + " is an anagram of " + s2);


  }
}

This is my program that works fine using toCharArray to compare anagrams, however would it be possible to do it finiding every 'a' to 'z' and append it to the sorted list instead of toCharArray?

---

Well there are a few options. If all you want to do is avoid the call to "toCharArray" then you can just loop through the string and create of characters that way, but I doubt this is what you're looking for?

You could also do an implementation as follows (pseudo-code):

public void areAnagrams(String s1, String s2)
{
  int[] aNumLetters = new int[26];

  s1.toLowerCase();
  s2.toLowerCase();

  for each char c in s1
    aNumLetters[(int)c - ((int)'a')]++;

  for each char c in s2
    aNumLetters[(int)c - ((int)'a')]--;

  for each int nLetterCount in aNumLetters
    if nLetterCount != 0
      return false

  return true;
}

---

I would consider a regular expression using the Pattern and Matcher classes to find characters within "[a-zA-Z]". You can then loop through the results

String string = "abcd123";
Pattern pattern = Pattern.compile("[a-zA-Z]");
Matcher matcher = pattern.matcher(string);
while (matcher.find()) {
    System.out.println(matcher.group());
}

---

If you do a naive search through a string for 'a' then 'b' and so on, then essentially you'll be performing a bubble sort which will have worse performance than Arrays.sort() which uses quicksort.

I would imagine the toCharArray() conversion has a negligible, one-time cost so trying to micro-optimize that away would be fruitless.

Instead—consider that for two strings to be anagrams it doesn't actually matter whether their sorted letters are equal, just that they have to contain the same number of each letter. That is, if a string contains 3 A's and 1 B and 2 N's then it's an anagram of BANANA.

Armed with that, we can conceivably compare whether two strings are anagrams simply by iterating through each character in the first string and building a Map of <Character, Integer> counts. Then iterate through the second string and do the reverse—decrement the count for each character.

After scanning the second string, you just need to check whether all counts are zero. One advantage of this approach is you can 'short-circuit' the checking whenever a character count goes below zero while scanning the second string—this means that the second string has more of that character than the first, so they're not anagrams.

The above outlines a best case O(n) algorithm (essentially, just one pass through each string) assuming best case of O(1) for map operations. On the worst case, we're looking at O(n^2), I think.

Contrast this to quicksort, which has the same worst-case performance but O(n log(n)) best case.

Of course, in practice quicksorting the character arrays might be faster for shorter strings. However, as the strings get substantially longer the above map-based algorithm should start to prove more efficient, esp. with the short-circuiting.

---

You can use a single String.replaceAll() to remove all non-alphabetic characters from the string, and then the rest of your code should be correct.

This is because String.replaceAll() uses regular expressions. Take a look at the javadocs for Pattern for a quick reference on regular expressions in Java. Pay special attention to the Character Classes section; from the examples you should be able to construct a pattern that matches "non-alphabetic characters". Use that pattern for the first parameter, and empty string for second parameter in String.replaceAll().

It's not the most efficient implementation in terms of performance, but probably is the simplest to code.