3
\$\begingroup\$

I am working on an interview question from Amazon Software:

Design an algorithm to take a list of strings as well as a single input string, and return the indices of the list which are anagrams of the input string, disregarding special characters.

I was able to design the algorithm fine. What I did in psuedocode was:

  1. Create an array character count of the single input string
  2. For each string the list, construct the an array character count
  3. Compare the character count of each string in list to single output string
  4. If same, add it to a list that holds all the indexes of anagrams
  5. Return that list of indices

Here is my implementation in Java (it works; I've tested it):

 public static List<Integer> indicesOfAnag(List<String> li, String comp){
    List<Integer> allAnas = new ArrayList<Integer>();
    int[] charCounts = generateCharCounts(comp);
    int listLength = li.size();
    for(int c=0;c<listLength; c++ ){ 
        int[] charCountComp = generateCharCounts(li.get(c));
        if(isEqualCounts(charCounts, charCountComp))
            allAnas.add(c);
    }
    return allAnas;
}
private static boolean isEqualCounts(int[] counts1, int[] counts2){
    for(int c=0;c<counts1.length;c++) {
        if(counts1[c]!=counts2[c]) 
            return false;
    }
    return true;
}
private static int[] generateCharCounts(String comp) {
    int[] charCounts = new int[26];
    int length = comp.length();
    for(int c=0;c<length;c++) {
        charCounts[Character.toLowerCase(comp.charAt(c)) - 'a'] ++;
    }
    return charCounts;
}

I think that this solution runs in \$O(n)\$ where n is the number of strings in the list (I'm not sure, so can someone verify?). What I am concerned about is the space complexity. I think the space complexity is \$O(n)\$ because I am creating \$n\$ copies of the 26 length array. Is there anything that I can do to reduce the amount of space I am using? I think this space will cumulate and add up.

\$\endgroup\$
2
\$\begingroup\$

You're making an assumption that these strings contain just letters. If there are spaces, digits, or letters with diacritics, then you'll end up with an ArrayIndexOutOfBoundsException.

isEqualCounts() is just a reimplementation of Arrays.equals(int[], int[]). If you choose not to use Arrays.equals(), then I suggest starting with assert counts1.length == counts2.length;.

A more robust strategy, which doesn't rely on the assumption that the text is purely alphabetic, would be to check whether each sorted array of characters matches the sorted array of characters of the reference string.

You could optionally add a quick-but-crude check by calculating a "summary" or "fingerprint" of each string that consists of its length and, say, the sum of all its characters. Any string whose fingerprint is different from the fingerprint of the reference could be immediately rejected. The strings with matching fingerprints could then be checked more thoroughly.

\$\endgroup\$
  • 1
    \$\begingroup\$ But counts1 will never be shorter than counts2, because I always generate arrays of length 26. \$\endgroup\$ – committedandroider Mar 2 '15 at 19:20
  • \$\begingroup\$ And how would it be better to have a sorted array of characters? You would still have to compare all of the characters anyways. \$\endgroup\$ – committedandroider Mar 2 '15 at 19:22
  • \$\begingroup\$ You're right about the assumption. Suppose I didn't have access to a built in char carry sort method. Could I just generate arrays of all ASCII values then( of length 256)? \$\endgroup\$ – committedandroider Mar 25 '15 at 0:47
  • \$\begingroup\$ You could do that. But then you would just be broadening the assumption to say that the strings contain just characters in ISO-8859-1, which may or may not be appropriate. You should either ask your interviewer for clarification or document your assumption in a comment. \$\endgroup\$ – 200_success Mar 25 '15 at 1:06

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.