生成字符串的所有 k 大小的字谜

Question

如果你看到了这个问题的副本，请随时link它，因为我以前没有见过这个问题。

对于面试问题，我有以下内容：

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"]

我想出了 (1) 的解决方案，方法是递归输入字符串减去它的第一个字符，并将第一个字符插入每个返回的字谜的每个位置：

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

任何人都可以为 (2) 提出 Java 或 Python 解决方案，签名 def anagrams(word, k = None) 或 Java List<String> anagrams(String word, int k)?

Answer 1

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)?

是的，如果您已经完成 1)，则执行 2) 几乎是微不足道的。

只列出相同的变位词列表，但只显示前 "k" 个字符。例如：

[狗、dgo、odg、ogd、gdo、gog]

变为：

[做、dg、od、og、gd、去]

哪个（被视为一个集合）与您的示例输出到 2) 的相同。即，相同的 k-anagrams 列表，但顺序不同。

def kanagrams(word,k):
    return [x[0:k] for x in set(anagram(word))]

Answer 2

我认为这是正确的解决方案：

from itertools import permutations

def anagrams(word, k=None):
   return [''.join(p) for p in permutations(word, k)]

生成字符串的所有 k 大小的字谜

Generate all k-size anagrams of a string

python

java

algorithm

recursion

permutation