java - 从多个字符生成排列

Question

我正在研究一个预测文本解决方案，并根据特定字符串的输入从 Trie 中检索所有单词，即“at”将给出以“at”作为前缀的所有单词。我现在的问题是，我们还应该通过按下这两个按钮返回所有其他可能性，移动电话上的按钮 2 和按钮 8，这也会给出由“au、av、bt、bu”组成的词, bv, ct, cu, cv”(其中大部分不会有任何实际单词。

任何人都可以提出解决方案以及我将如何进行此操作以计算不同的排列？
(目前，我正在提示用户输入前缀(现在不使用 GUI)

Answer 1

欢迎使用递归和组合爆炸等概念:)

由于组合爆炸，您必须对此“聪明”:如果用户想要输入一个合法的 20 个字母的单词，那么您的解决方案“挂起”愚蠢地尝试数千万种可能性是 Not Acceptable 。

因此，您应该只在特里至少有一个前缀条目时进行递归。

这是一种生成所有前缀并且仅在匹配时递归的方法。

在这个例子中，我伪造了一个总是说有一个条目的尝试。我在五分钟内完成了这个，所以它肯定可以美化/简化。

这种解决方案的优点是，如果用户按下一个、两个、三个、四个或“n”键，它就可以工作，而无需更改您的代码。

请注意，当单词太多时，您可能不想添加所有以 'x' 字母开头的单词。由您来找到最符合您需要的策略(等待更多按键以减少候选或添加最常见的匹配作为候选等)。

private void append( final String s, final char[][] chars, final Set<String> candidates ) {
        if ( s.length() >= 2 && doesTrieContainAnyWordStartingWith( s ) ) {
            candidates.add( s + "..." ); // TODO: here add all words starting with 's' instead of adding 's'
        }
        if ( doesTrieContainAnyWordStartingWith( s ) && chars.length > 0 ) {
            final char[][] next = new char[chars.length-1][];
            for (int i = 1; i < chars.length; i++) {
                next[i-1] = chars[i];
            }
            // our three recursive calls, one for each possible letter
            // (you'll want to adapt for a 'real' keyboard, where some keys may only correspond to two letters)
            append( s + chars[0][0], next, candidates );
            append( s + chars[0][1], next, candidates );
            append( s + chars[0][2], next, candidates );
        } else {
            // we do nothing, it's our recursive termination condition and
            // we are sure to hit it seen that we're decreasing our 'chars'
            // length at every pass  
        }
    }

    private boolean doesTrieContainAnyWordStartingWith( final String s ) {
        // You obviously have to change this
        return true;
    }

注意递归调用(仅当有匹配的前缀时)。

您可以这样称呼它:我伪造用户按“1”，然后按“2”和“3”(我在我创建的 chars char[][] 数组中伪造了这个):

    public void testFindWords() {
        // Imagine the user pressed 1 then 2 then 3
        final char[][] chars = {
                {'a','b','c'},
                {'d','e','f'},
                {'g','h','i'},
        };
        final Set<String> set = new HashSet<String>();
        append( "", chars, set ); // We enter our recursive method
        for (final String s : set ) {
            System.out.println( "" + s );
        }
        System.out.println( "Set size: " + set.size() );
}

该示例将创建一个包含 36 个匹配项的集合，因为我“伪造”了每个前缀都是合法的并且每个前缀都指向一个单词(并且我只在“单词”由至少两个字母组成时添加了它)。因此 3*3*3 + 3*3，得到 36。

您可以尝试代码，它完全可以工作，但您当然必须对其进行调整。

在我的假示例中(用户按 1,2 然后按 3)，它创建了这个:

cdh...
afi...
adi...
beg...
cf...
adh...
cd...
afg...
adg...
bei...
ceg...
bfi...
cdg...
beh...
aeg...
ce...
aeh...
afh...
bdg...
bdi...
cfh...
ad...
cdi...
ceh...
bfh...
aei...
cfi...
be...
af...
bdh...
bf...
cfg...
bfg...
cei...
ae...
bd...
Set size: 36

欢迎来到真正的编码:)