查找字符串的变体(只有删除，没有换位)

Question

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

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);
        }
    }
}

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

Answer 1

以下代码将使您能够获得所有可能性(如果需要，请记住添加word本身)。这个想法是检索删除一个字符的所有可能性(例如hello结果在ello hllo helo hell)。这些结果可依次用于获得删除两个字符的可能性(再次删除一个字符)。导致llo elo ell为ello，依此类推…

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()的方法是另一个不错的选择。您可以运行一些测试，看看哪个性能更好，以决定使用哪个。注意，使用后者可能会在private方法中删除对if的需要。

Answer 2

我会使用完全不同的算法:我会找到所有重复(ll) (oo) (ll) (oo)等。，保存一个数组，描述它们在文本中的位置，以及每次重复的字符计数。
例:数组A =
[l | 2]
[o | 2]

。
。。

然后我说有第二个数组，初始计数为0，然后增加计数并打印出所有排列

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

步骤2:(增量计数)
B =
[l | 2]
[o | 1]
==>打印hello

第三步:
B =
[l|3] ==>大于max，所以现在将其重置为0，并增加第二个单元格，所以它变成:
B =
[l | 1]
[o | 2]

第4步:(再次增加第一个元素)
[l|2] ==>不大于max，所以没有溢出，所以保持这个状态
[o | 2]
==>打印hello