java - 查找加起来等于给定字符串的所有子字符串组合

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]