It looks as if it would involve permutations and combinations both of the letters or a union of permutations and combinations for n letters. Surprisingly, it is much simpler.
Below are the possible words for letters 'abc'. I have highlighted the patterns in them.
a
ab
abc
ac
acb
b
ba
bac
bc
bca
c
ca
cab
cb
cba
For n letters, it looks like we have to get permutations of n letters plus permutations of n-1 letters and so on till permutations of each letter which is O(nPn) + O(n-1Pn-1) + ... O(1P1). The time complexity is O(n!) + O(n-1!) + ... + O(1!) = O(n!).
All possible words for n letters can be obtained by using the permutations algorithm of n letters with a very simple mod in O(n!) time itself. The changes are in blue.
permutation(char[] in):
//initially, used[] set to false and depth is 0
permuteWords(in, out, used, 0)
permuteWords(char[] in, buffer out, bool[] used, int depth):
if depth > 0:
print(out)
if depth == in.length:
print(out)
return
for (int i = 0; i < in.length; i++):
if used[i] == true:
continue
used[i] = true
out.append(in[i])
permuteWords(in, used, out, depth +1)
out.length = out.length -1
used[i] = false
Time complexity is the same as that of permutation algorithm O(n!).
A better way is to have each word added to a list (the list would be created in
permutation
method and passed as parameter to permuteWords
method) for extensions of the problem. Possible extensions to this scrabble problem are:
- Find the longest word.
- Find the word with maximum points given a map of points to each letter.
- You have a dictionary, how would you use it to get the valid words? For this, I would assume that the dictionary has a function like boolean isValidWord(String s) which would indicate if a particular word is valid or not. Here is another interesting thought with the dictionary extension which requires a trie structure. I could use a dictionary, to see if I can bust out of permuting further as mostly not all permutations are going to be valid words. For example, if you have a dictionary implemented as a trie with a function boolean hasPrefix(String s) or hasPrefix(char c) and letters 'aabc' and suppose that the dictionary does not have a trieNode structure a-a, you do not have to permute further for the unused characters 'bc'. Below is the changed code that I came up with (not tested).
Set getValidWordsPermutation(char[] in):
Set validWords = new HashSet();
//initially, used[] set to false and depth is 0
permuteWords(in, out, used, 0, validWords);
return validWords;
permuteWords(char[] in, buffer out, bool[] used, int depth, Set validWords):
// if the current prefix is not present in the dictionary, then do not permute further with the rest of the unused letters
if !dict.hasPrefix(out): //or dict.hasPrefix(out[out.length()])
return
if depth == in.length:
return
for (int i = 0; i < in.length; i++):
if used[i] == true:
continue
used[i] = true
out.append(in[i])
//if current prefix is a word, add to the set
if dict.isValidWord(out):
validWords.add(out)
permuteWords(in, used, out, depth +1, validWords)
out.length = out.length -1
used[i] = false
Using the dictionary, only those trieNodes forming valid words possible from the n letters are traversed in the dictionary trie [O(|V|+|E|) time] and not all permutations [O(n!) time]. If all permutations are valid words OR if there is no such hasPrefix(String s) function for trie, then it takes O(n!) time - which is better than O(nCn * n!) + O(nCn-1 * n-1!) + ... O(nC1 * 1!).
[Hat tip to OJ]
This comment has been removed by the author.
ReplyDeleteThanks alot man , u r a genius !!
ReplyDeleteThanks for posting. The code helped me a lot with a project.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete