制作不同单词长度的单词列表？

Question

我想创建具有不同单词长度的单词列表。我的 src for...

length=1:

for(int a=97;a<=122;a++)
   String foo=String.valueOf((char)a);

length=2:

for(int a=97;a<=122;a++)
    for(int b=97;b<=122;b++) 
       String foo=String.valueOf((char)a+""+(char)b);

有什么想法如何改进此代码，使其独立于实际的字符串长度？

Answer 1

如果你的字符串是一个数字，你只需加一直到数字溢出就可以得到所有可能的值。

您可以对字符串使用相同的方法；只需将每个字符视为一个数字即可；在最右边的字符添加一个；如果换行，则增加下一个字符，依此类推。

// for strings of size N
char *str = malloc(N+1);
// init
str[N] = 0;
for (i=0, i<N, i++) str[i]='a';

int done = 0;
while (!done)
{
    for(i=N-1; i>=0; i--)
    {
        str[i] += 1;
        if (str[i] == 'z'+1) 
        {
            if (N==0) done = 1;
            str[i] = 'a';
        }
        else break;
    }
    // do something with str
}

Answer 2

请注意，下面的这种方法效率相当低。通过使用使用字符串构建器的辅助方法，然后在完成后完成主要方法中的字符串，可以提高效率。

无论如何，递归是处理这个问题的最佳方法。

List<String> generate(int len) {
    if(len == 1) {
        List<String> strings = new LinkedList<String>();
        // notice I'm putting a char here, not an int
        for(char a=97;a<=122;a++) strings.add(String.valueOf(a));
        return strings;
    }
    List<String> shortStrings = generate(len - 1);
    List<String> strings = new LinkedList<String>();
    for(String shortString : shortStrings)
        for(char a=97;a<=122;a++) strings.add(shortString + A);
    return strings;
}

Answer 3

正如 Tejs 所建议的，您将需要使用递归。您无法编写具有动态深度的循环，但您可以递归到您想要的任何级别（至少直到您用完堆栈空间为止）：

//Pseudocode!
void generate(dictionary, string, depth)
{
    if(depth == 0)
    {
        dictionary.add(string);
    }
    else
    {
        for(char c = 'a'; c <= 'z'; ++c)
        {
            generate(dictionary, string + c, depth - 1);
        }
    }
}

只需开始 if off 像：

dictionary = new Dictionary;
generate(dictionary, '', depth);

然后您就结束了。如果您想要包含达到所需长度的所有字符串，这是一个简单的调整 - 只需始终将字符串添加到字典中，但仅在当前深度大于零时才递归。

希望这有帮助！

Answer 4

如果我没有完全错的话，您要做的就是生成长度为 <=N 的所有可能的字符串。

最简单的方法是将其映射到生成数字的方式，即将一个数字加 1 以获得下一个数字。所以基本上从 "a" 开始，然后加 1 得到 "b" 等等，直到 "z"。现在添加 1 将导致结转，因此生成 "aa"，然后生成 "ba" 等等，直到 "za" 从哪里它变成“ab”。

如果您可以将自然数映射到字符串，则可以极大地简化这一过程。要获取字符串，只需执行以下操作：

string getString(int val) {
    string str = "";
    while (val>=0) {
        int rem = val%26; // as there are 26 characters in english
        str = str + charToString('a'+rem);
        val /= 26;
    }
    return str;
}

现在只需调用此函数即可获取字符串：

void listStrings(int N) {
    int max = 26^N-1;
    string str;
    for(int i=1; i<=max; ++i) {
        str = getString(i);
        doSomething(str); // maybe print it or store in file
    }
}

我希望这对您有帮助。