生成单词所有变体的算法

问题描述

我想通过下面的例子来解释我的问题.

i would like to explain my problem by the following example.

假设单词:abca 有变体:ä, à
b 没有变体.
c 有变体:ç

assume the word: abca has variants: ä, à
b has no variants.
c has variants: ç

所以可能的词是:

美国广播公司
äbc
àbc
abç
äbç
àbç

abc
äbc
àbc
abç
äbç
àbç

现在我正在寻找一种算法来打印带有任意字母变体的 abritray 单词的所有单词变体.

now i am looking for the algorithm that prints all word variantions for abritray words with arbitray lettervariants.

推荐答案

我建议您递归地解决这个问题.下面是一些 Java 代码供您开始使用:

I would recommend you to solve this recursively. Here's some Java code for you to get started:

static Map<Character, char[]> variants = new HashMap<Character, char[]>() {{
    put('a', new char[] {'ä', 'à'});
    put('b', new char[] {        });
    put('c', new char[] { 'ç'    });
}};

public static Set<String> variation(String str) {

    Set<String> result = new HashSet<String>();

    if (str.isEmpty()) {
        result.add("");
        return result;
    }

    char c = str.charAt(0);
    for (String tailVariant : variation(str.substring(1))) {
        result.add(c + tailVariant);
        for (char variant : variants.get(c))
            result.add(variant + tailVariant);
    }

    return result;
}

测试:

public static void main(String[] args) {
    for (String str : variation("abc"))
        System.out.println(str);
}

输出:

abc
àbç
äbc
àbc
äbç
abç

这篇关于生成单词所有变体的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！