0

给定一个字符串，我想找到所有没有换位的变体，只有删除。例如，给定字符串：

helloo

变体列表如下（由空格分隔）。

helloo hello heloo helo

到目前为止我的解决方案是遍历每个字符，然后如果当前字符匹配下一个字符，则递归尝试原始和删除的字符版本，如下所示。

// takes String with at most two consecutive characters of any character, 
// and returns an Iterable of all possible variants (e.g. hheello -> heello, hhello, ...)
private static Iterable<String> findAllVariants(String word) {
    StringBuilder variant = new StringBuilder(word);
    Queue<String> q = new LinkedList<String>();
    findAllVariants(word, variant, 0, q);
    return q;
}

// helper method
private static void findAllVariants(String word, StringBuilder variant, int currIndex, Queue<String> q) {
    if (currIndex == variant.length() - 1) q.add(variant.toString());

    for (int i = currIndex; i < variant.length() - 1; i++) {
        char thisChar = variant.charAt(i);
        char nextChar = variant.charAt(i+1);
        if (thisChar == nextChar) {
            // get all variants with repeat character
            findAllVariants(word, variant, i+1, q);

            // get all variants without repeat character;
            variant = variant.deleteCharAt(i);
            findAllVariants(word, variant, i, q);
        }
    }
}

然而，我最终得到了大量的答案副本，而其他的都没有。当我在纸上做我的算法时，它似乎是正确的。我究竟做错了什么？

4

2 回答 2

1

类似于以下代码的内容将使您获得所有可能性（word如果需要，请记住添加自身）。这个想法是检索删除一个字符的所有可能性（例如hello结果ello hllo helo hell）。这些结果又可以用来获得删除两个字符的可能性（再次删除一个字符）。导致llo elo ellforello等...

List<String> getPossibilities(String word) {
    int removeChars = word.length() - 1;
    List<String> possibilities = new ArrayList();
    List<String> options = Arrays.asList(word);
    for(int i = 0; i <= removeChars; i++) {
        List<String> results = new ArrayList();
        for(String option : options) {
          for(String result : removeOneChar(option)) {
                if(!results.contains(result)) {
                    results.add(result);
                }
            }
        }
        possibilities.addAll(results);
        options = results;
    }
    return possibilities;
}

private static List<String> removeOneChar(String word) {
    List<String> results = new ArrayList();
    for(int i = 0; i < word.length(); i++) {
        int secondPart = i + 2;
        if(secondPart <= word.length()) {
            results.add(
                    word.substring(0, i) 
                    + word.substring(i + 1, word.length()));
        }
        else {
            results.add(
                    word.substring(0, i));
        }
    }
    return results;
}

请注意if(!contains(result))以防止任何重复。

注意我已经substring()完成了这个，你的方法removeCharAt()是另一个不错的选择。您可以运行一些测试以查看哪个性能更好来决定使用哪个。注意使用后者可能会消除方法中的if需要private。

于 2013-05-15T06:51:02.823 回答
0

我会使用相当不同的算法：我会找到所有重复 (ll) (oo) (llll) (ooo) 等，保留一个数组来描述它们在文本中的位置，以及每次重复的字符数。
例如数组 A =
[l|2]
[o|2]
。
.
.

然后我会说第二个数组的初始计数为零并在那里增加计数并打印出所有排列：

数组 B =
[l|1]
[o|1]
==> 打印 helo

步骤 2：（递增计数）
B =
[l|2]
[o|1]
==> 打印 hello

步骤 3：
B =
[l| 3] ==> 大于最大值，所以将其重置为 0，现在增加第二个单元格，所以它变成：
B =
[l|1]
[o|2]
==> 打印 heloo

第 4 步：（再次增加第一个元素）
[l|2] ==> 不大于最大值，所以不会溢出，所以保持这种状态
[o|2]
==> 打印 hello

于 2013-05-15T05:43:34.757 回答