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

问题描述

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

I'm trying to create a data structure that holds all the possible substring combinations that add up to the original string. For example, if the string is "java" the valid results would be "j", "ava", "ja", "v", "a", an invalid result would be "ja", "a" or "a", "jav"

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

I had it very easy in finding all the possible substrings

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

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

and now I'm trying to construct a structure that holds only the valid substrings. But its not nearly as easy. I'm in the mist of a very ugly code, fiddling around with the indexes, and no where near of finishing, most likely on a wrong path completely. Any hints?

推荐答案

以下是一种方法：

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]

这篇关于找到添加到给定字符串的所有子串组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！