Paul
BAN USERpackage careercup;
public class Scribble {
public static List<String> findDictionaryWords3rd(char[] letters, String[] words) {
List<String> _result = new ArrayList<String>();
final int[] indexedAlphabet = indexAlphabet(letters);
for (String word : words) if (testWord(word, indexedAlphabet)) _result.add(word);
return _result;
}
private static boolean testWord(String word, int[] indexedAlphabet) {
final int[] alphabet = indexedAlphabet.clone();
for (char z : word.toCharArray()) {
if (--alphabet[(z - 'a')] < 0) return false;
}
return true;
}
private static int[] indexAlphabet(char[] letters) {
final int[] result = new int[26];
for (char z : letters) result[z - 'a'] += 1;
return result;
}
}
A little optimized example, but the idea the same.
- Paul January 18, 2014thanks for review. That was big fail ;)
> Also, k can be up to n^2, so the first double loop can take n^2
in original problem need to return first K elements, not just Kth element which was described as PS, that's why at least need to fill K elements. So algorithm's expected complexity is O(K). If K is equal to max value n^2, do you know any algorithm which fill n^2 elements in O(N)?
I think
should be complexity O(1) but adding O(n logn), so need to ask interviewer what operation is most often and sort points on adding or on searching.
- Paul February 10, 2014