Decide if two strings are anagrams

Write a method to decide if two strings are anagrams or not.

My initial thoughts:

  1. Build up hash maps for the two strings and check if the two hash maps are identical

My initial codes:

	public static boolean areAnagrams(String a, String b) {
		Map<Character, Integer> mapA = new HashMap<Character, Integer>();
		Map<Character, Integer> mapB = new HashMap<Character, Integer>();
		for (int i = 0; i < a.length(); ++i) {
			int count;
			count = mapA.get(a.charAt(i)) == null ? 1
					: mapA.get(a.charAt(i)) + 1;
			mapA.put(a.charAt(i), count);

			count = mapB.get(b.charAt(i)) == null ? 1
					: mapB.get(b.charAt(i)) + 1;
			mapB.put(b.charAt(i), count);
		}
		return mapA.equals(mapB);
	}

Comments after running:

  1. If the two strings are not the same size, exception! We should check the length of the two strings, if they are not the same, then return false in the first place.
  2. Otherwise it works fine. Time complexity O(n), space complexity O(n)

Solution:
The idea is from the solution and then I re-write it again.

	public static boolean anagrams(String a, String b) {
		if (a.length() != b.length())
			return false;

		int unique_chars = 0;
		int[] table = new int[256];
		// the same process as build a <char,int> mapping.
		// also count the number of unique characters.
		for (int i = 0; i < a.length(); ++i) {
			if (table[a.charAt(i)] == 0)
				unique_chars++;
			table[a.charAt(i)]++;
		}

		int unique_char_count = 0;
		for (int i = 0; i < b.length(); ++i) {
			if (table[b.charAt(i)] == 0) {
				// found char in b that is not in a
				return false;
			}
			// check. this char is done processing.
			table[b.charAt(i)]--;

			if (table[b.charAt(i)] == 0) { // if all of the occurrences of that
											// char has been checked
				unique_char_count++;
				if (unique_char_count == unique_chars) // if the number of
														// unique chars in b is
														// the same as in a
					return i == b.length() - 1; // final check if this is the
												// end of b
			}
		}
		return false;
	}

Comments:

  1. Check for the length of two strings first.
  2. The idea of building up hash-table for one string and then trying to match it against the second string should be remarked.

The simplest solution, if allowed:

boolean anagram(String s, String t) {
  return sort(s) == sort(t);
}
Advertisements

2 Comments (+add yours?)

  1. neil
    Jul 07, 2012 @ 01:46:35

    tanx

    Reply

  2. Shruthi
    Mar 14, 2014 @ 12:22:51

    should we hav to check for unique characters ? Since there r lots of other checks in the code .. like length null etc! Cant we just stop once we reach the end of second string?

    public boolean isAnagram(String strOne,String strTwo) {
    if(strOne == null || strTwo == null) {
    return false;
    }

    if(strOne.length() != strTwo.length()) {
    return false;
    }

    int[] letters=new int[256];
    for(int i=0;i<strOne.length();i++) {
    int character=strOne.toLowerCase().charAt(i);
    ++letters[character];
    }

    for(int j=0;j<strTwo.length();j++) {
    int character=strTwo.toLowerCase().charAt(j);
    if(letters[character]==0) {
    return false;
    }
    –letters[character];
    if(j==strTwo.length()-1) {
    return true;
    }
    }
    return false;
    }

    Something like this?

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: