查找所有与给定字符串相加的子字符串组合

一尘不染

查找所有与给定字符串相加的子字符串组合

algorithm

我正在尝试创建一个数据结构，该数据结构包含所有可能的子字符串组合，这些组合加总到原始字符串。例如，如果字符串是"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);

现在我正在尝试构建仅包含有效子字符串的结构。但这并不容易。我陷入了一个非常丑陋的代码中，徘徊在索引周围，并且几乎没有完成的可能，很可能是完全在错误的路径上完成的。有什么提示吗？

阅读 344

2020-07-28

共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]

2020-07-28