Alexandru Mihai
BAN USERI keep a hash with the sorted word as key.To sort a word i use an array of 26 elements, each representing a letter.
def sort_anagrams(words = []):
dict_words, sorted_words = {}, []
for word in words:
letters = [0] * 26
for letter in word:
letters[ord(letter) - 97] += 1
new_word = ''
for key, value in enumerate(letters):
new_word += chr(key + 97) * value
try:
dict_words[new_word].append(word)
except KeyError:
dict_words[new_word] = [word]
for words in dict_words.values():
for word in words:
sorted_words.append(word)
return sorted_words
I consider the numbers are previously added in the hash.
bool addsUp(vector <int> &input, int target) {
for (int i = 0; i < input.size(); i++) {
int index = abs(target - input[i]) % KEY;
for (int j = 0; j < hash[index].size(); j++) {
if (target - input[i] == hash[index][j])
return true;
}
}
return false;
}
void BFS() {
int i, j, k;
q.push_back(1), r.push_back(1);
done[1] = true;
niv[1] = 1;
for (i = 0; i < q.size(); i++) {
k = q[i];
for (j = 0; j < L[k].size(); j++) {
q.push_back( L[k][j] );
niv[ L[k][j] ] = niv[k] + 1;
if (!done[ niv[ L[k][j] ] ]) r.push_back(L[k][j]);
done[ niv[ L[k][j] ] ] = true;
}
}
for (i = 0; i < r.size(); i++)
printf("%d ", r[i]);
}
It's called the turtle and the rabbit algorithm. O(n).
- Alexandru Mihai October 13, 2013