java - 根据 Java 中特定字母规则替换生成可能的单词组合

Question

我在找出递归生成特定字母组合的最佳方法时遇到了一些困难。

目前，我有一种方法可以更改字符串并更改某些字符以创建单词的单个替换。

但是，这不能满足单词的不同组合。例如，如果我有单词 kjng ，通常会被误认为是打印机字符，例如:

[j=>i, i=>j, v=>u, u=>v, s=>f, f=>s, uu=>w, vv=>w]  (map lookup, "=>" this is symbolic for key, value representation to make it extra clear) 

基于这种方法，这个词将成为国王。对于只有一种可能性的词来说这很好。然而 murdir 随之而来，它应该生成以下内容:

  murdir
  mvrdjr
  mvrdir
  murdjr

对此提供一些建议会很好，目前我不确定如何最好地管理这种情况。例如，如何跟踪更改，以字符 block 的形式进行(1，然后 2，然后 3，等等)。

Answer 1

人们按照某种规则在某个位置改变一个单词。然后进一步递归。如果已经找到新单词，则停止这种情况。

所以基本上你迭代了wordIndex 和ruleIndex。递归公式是最简单的，以后可以改为迭代。您可以进行两级递归:遍历规则、遍历单词内部。

好的，在java中:

public class Solver {

    public static void main(String[] args) {
        System.out.println("Solver");
        Solver solver = new Solver("j=>i", "i=>j", "v=>u", "u=>v", "s=>f",
            "f=>s", "uu=>w", "vv=>w");
        //Set<String> words = solver.determineAllWords("murdir");
        Set<String> words = solver.determineAllWords("gigi");
        words.forEach(System.out::println);
        System.out.println("Done");
    }

    static class Rule {
        String from;
        String to;

        public Rule(String from, String to) {
            this.from = from;
            this.to = to;
        }
    }

    private final Rule[] rules;

    public Solver(String... tofroms) {
        this.rules = new Rule[tofroms.length];
        for (int i = 0; i < rules.length; ++i) {
            String[] tofrom = tofroms[i].split("=>", 2);
            rules[i] = new Rule(tofrom[0], tofrom[1]);
        }
    }

    public Set<String> determineAllWords(String word) {
        Set<String> solutionWords = new TreeSet<String>(); // Could be a field too.
        solutionWords.add(word);
        int ruleIndex = 0;
        int wordIndex = 0;
        solveTryingRules(solutionWords, word, wordIndex, ruleIndex);
        return solutionWords;
    }

    private void solveTryingRules(Set<String> solutionWords,
            String word, int wordIndex, int ruleIndex) {
        if (ruleIndex >= rules.length) {
            return;
        }
        Rule rule = rules[ruleIndex];
        int wordIndexFound = word.indexOf(rule.from, wordIndex);
        if (wordIndexFound == -1) {
            // Next rule:
            solveTryingRules(solutionWords, word, 0, ruleIndex + 1);
        } else {
                // Keep at same rule, 
            // Not applying rule to found word position:
            solveTryingRules(solutionWords, word, wordIndexFound + 1, ruleIndex);

            // Applying rule to found word position:
            String nextWord = word.substring(0, wordIndexFound)
                    + rule.to
                    + word.substring(wordIndexFound + rule.from.length());
            boolean added = solutionWords.add(nextWord);
            if (added) {
                solveTryingRules(solutionWords, nextWord, 0, 0);
            }
        }
    }
}