2

If you've seen a duplicate to this question, please feel free to link it because I haven't seen this question before.

For an interview question, I had the following:

1) Generate all anagrams of a string
   Ex. anagrams("dog") -> ["dog","dgo","odg","ogd","gdo","god"]

2) Generate all k-size anagrams of a string
   Ex. anagrams("dog",k = 2) -> ["do","od","dg","gd","go","og"]

I came up with a solution to (1) by recursing on an input string minus its first char, and inserting the first char into every position of every returned anagram:

def anagrams(word):
    if len(word) == 1:
        return [word]
    current = word[0]
    anags = []
    for anag in anagrams(word[1:]):
        anags += [anag[:i] + current + anag[i:] for i in range(len(anag) + 1)]
    return anags

Can anyone come up with Java or Python solution for (2) with the signature def anagrams(word, k = None) or in Java List<String> anagrams(String word, int k)?

ShaharZ
  • 389
  • 5
  • 11
  • http://stackoverflow.com/a/104436/2337736 - though note that that will include duplicates if there are duplicate letters in the input string. From your examples I can't tell if that matters to you - if it does I'd probably just use `set` to dedupe. – Peter DeGlopper Sep 22 '15 at 22:44
  • This would be the best way to do it, but perhaps wouldn't have impressed the people in your interview other than your handy knowledge of existing libraries. It might be worthwhile to work through **how** these work. Good luck. – Shawn Mehan Sep 22 '15 at 22:49
  • @PeterDeGlopper nice. Dupes do matter. Getting k = n permutations results in no duplicates, but for the k < n case, like you said, can use sets instead of lists and do a union. – ShaharZ Sep 22 '15 at 22:50
  • You can still get dupes with k=n - consider input "foo". The permutation algorithms won't detect that the two "o"s are the same character. Anyway, yeah, if I were interviewing I would add points for knowing that there's a standard library solution - knowing to find a pre-written implementation is actually a vital skill IMO - and then ask the interviewee to work on their own version. – Peter DeGlopper Sep 22 '15 at 22:52
  • I like your solution, @ShaharZ. – Matthew Cornell Sep 24 '15 at 16:38

2 Answers2

1

I believe this is the correct solution:

from itertools import permutations

def anagrams(word, k=None):
   return [''.join(p) for p in permutations(word, k)]
Chad S.
  • 6,252
  • 15
  • 25
  • That's what I'd do in a real life coding scenario, but for an interview I'd say something like "If I was doing this project myself, I'd probably use `permutations`, but if it wasn't available, I'd code it like this...' And then do the exercise. – Matthew Cornell Sep 24 '15 at 15:57
0

For an interview question, I had the following:

1) Generate all anagrams of a string
   Ex. anagrams("dog") -> ["dog","dgo","odg","ogd","gdo","god"]

2) Generate all k-size anagrams of a string
   Ex. anagrams("dog",k = 2) -> ["do","od","dg","gd","go","og"]

I came up with a solution to (1) by recursing on an input string minus its first char, and inserting the first char into every position of every returned anagram:

def anagrams(word):
    if len(word) == 1:
        return [word]
    current = word[0]
    anags = []
    for anag in anagrams(word[1:]):
        anags += [anag[:i] + current + anag[i:] for i in range(len(anag) + 1)]
    return anags

Can anyone come up with Java or Python solution for (2) with the signature def anagrams(word, k = None) or in Java List<String> anagrams(String word, int k)?

Yes, it's almost trivial to do 2) if you have already done 1).

Just list the same list of anagrams, but only display the first "k" characters. For example:

[dog,dgo,odg,ogd,gdo,gog]

becomes:

[do,dg,od,og,gd,go]

which (considered as a set) is the same the your example output to 2). I.e., the same list of k-anagrams but in a different order.

def kanagrams(word,k):
    return [x[0:k] for x in set(anagram(word))]
hft
  • 1,245
  • 10
  • 29