找到添加到给定字符串的所有子串组合

Question

我正在尝试创建一个数据结构,其中包含所有可能的子字符串组合,这些组合可以添加到原始字符串中.例如,如果字符串是"java"有效的结果将是"j", "ava","ja", "v", "a"一个无效的结果将是"ja", "a"或"a", "jav"

我很容易找到所有可能的子串

    String string = "java";
    List<String> substrings = new ArrayList<>();
    for( int c = 0 ; c < string.length() ; c++ )
    {
        for( int i = 1 ; i <= string.length() - c ; i++ )
        {
            String sub = string.substring(c, c+i);
            substrings.add(sub);
        }
    }
    System.out.println(substrings);

现在我正在尝试构建一个只包含有效子串的结构.但它并不那么容易.我正处于一个非常丑陋的代码的迷雾中,摆弄着索引,并且没有接近完成,很可能完全是错误的路径.任何提示？

Answer 1

这是一种方法:

static List<List<String>> substrings(String input) {

    // Base case: There's only one way to split up a single character
    // string, and that is ["x"] where x is the character.
    if (input.length() == 1)
        return Collections.singletonList(Collections.singletonList(input));

    // To hold the result
    List<List<String>> result = new ArrayList<>();

    // Recurse (since you tagged the question with recursion ;)
    for (List<String> subresult : substrings(input.substring(1))) {

        // Case: Don't split
        List<String> l2 = new ArrayList<>(subresult);
        l2.set(0, input.charAt(0) + l2.get(0));
        result.add(l2);

        // Case: Split
        List<String> l = new ArrayList<>(subresult);
        l.add(0, input.substring(0, 1));
        result.add(l);
    }

    return result;
}

输出:

[java]
[j, ava]
[ja, va]
[j, a, va]
[jav, a]
[j, av, a]
[ja, v, a]
[j, a, v, a]