找出所有能够相加得到给定字符串的子字符串组合

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

现在我正在尝试构建一个仅包含有效子字符串的结构。但这并不容易。我正处于非常丑陋的代码中，摆弄索引，离完成还差得远，很可能完全走错了方向。有什么提示吗？

- learnAndImprove

---

假设你指的是正确的子字符串，因为空字符串也是一个子字符串。 - aioobe

不，这与结构无关，我正在构建一个Set<List<String>>，但它甚至可以是一个二维数组，我的问题在于逻辑，如何找到合适的子字符串。 - learnAndImprove

@aioobe 是的，合适的非空子字符串。 - learnAndImprove

你应该尝试递归：取第一个字符，分割或不分割，然后对其余部分进行划分。 - tobias_k

这段代码甚至无法编译。C和i的数据类型是什么？ - akhil_mittal

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]

- aioobe

---

我印象深刻。为了发表评论需要更多字数，所以我只会重复一遍——我印象深刻。 - learnAndImprove

感谢发布。非常棒的面试题练习。我发现这类问题很难快速得到正确答案。 - aioobe

对我来说，这确实很难，额外的诀窍是它看起来很容易，直到你真正尝试过，再次感谢。 - learnAndImprove

你真是太棒了！能否请给我 JavaScript 版本的代码？当我尝试在 JavaScript 中执行时，我的浏览器会卡住。 - kashyaphp

请注意，对于长度为n的字符串，有2^(n-1)个结果，因此不要使用太大的输入进行尝试。 @kashyaphp https://jsfiddle.net/u49qu6ut/ - aioobe

Answer 2

也许有人希望另一种非递归且不需要保存列表的解决方案：

public static List<List<String>> substrings(final String input) {
    if(input.isEmpty())
        return Collections.emptyList();
    final int size = 1 << (input.length()-1); 
    return new AbstractList<List<String>>() {

        @Override
        public List<String> get(int index) {
            List<String> entry = new ArrayList<>();
            int last = 0;
            while(true) {
                int next = Integer.numberOfTrailingZeros(index >> last)+last+1;
                if(next == last+33)
                    break;
                entry.add(input.substring(last, next));
                last = next;
            }
            entry.add(input.substring(last));
            return entry;
        }

        @Override
        public int size() {
            return size;
        } 
    };
}

public static void main(String[] args) {
    System.out.println(substrings("java"));
}

输出：

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

它只是根据索引计算下一个组合。

- Tagir Valeev

---

我喜欢这个解决方案！！ - akhil_mittal

使用列表数组而不是列表嵌套列表更为合理。数组索引应对应字符串分割成子字符串的方式。例如，第6个元素应对应二进制数110，这将在第一个位置不放逗号，在第二个位置放置逗号，在第三个位置放置逗号：[ja,v,a]。 - Edward Doolittle

@EdwardDoolittle，对于列表数组，需要将所有组合实际存储到内存中，因为在Java中无法动态计算数组。我也做了同样的事情，但是针对列表索引。 - Tagir Valeev

Answer 3

如果有人想在Python中寻找相同的算法，这里提供Python实现：

from itertools import combinations

def compositions(s):
    n = len(s)
    for k in range(n):
        for c in combinations(range(1, n), k):
            yield tuple(s[i:j] for i, j in zip((0,) + c, c + (n,)))

例子如何工作：

>>> for x in compositions('abcd'):
...     print(x)
('abcd',)
('a', 'bcd')
('ab', 'cd')
('abc', 'd')
('a', 'b', 'cd')
('a', 'bc', 'd')
('ab', 'c', 'd')
('a', 'b', 'c', 'd')

通过小的修改，您可以按不同的顺序生成组合：

def compositions(s):
    n = len(s)
    for k in range(n):
        for c in itertools.combinations(range(n - 1, 0, -1), k):
            yield tuple(s[i:j] for i, j in zip((0,) + c[::-1], c[::-1] + (n,)))

它会给你这个：

>>> for x in compositions('abcd'):
...     print(x)
('abcd',)
('abc', 'd')
('ab', 'cd')
('a', 'bcd')
('ab', 'c', 'd')
('a', 'bc', 'd')
('a', 'b', 'cd')
('a', 'b', 'c', 'd')

通过添加一个小功能，您可以仅生成指定数量的拆分：

def compositions(s, r=None):
    n = len(s)
    r = range(n) if r is None else [r - 1]
    for k in r:
        for c in itertools.combinations(range(n - 1, 0, -1), k):
            yield tuple(s[i:j] for i, j in zip((0,) + c[::-1], c[::-1] + (n,)))

>>> for x in compositions('abcd', 3):
...     print(x)
('ab', 'c', 'd')
('a', 'bc', 'd')
('a', 'b', 'cd')

- sirex

Answer 4

看起来这是查找字符串长度的组合的问题，并使用这些组合制作子字符串。因此，一个数字n有2^n-1种组合方式，对于较长的字符串可能会耗费一些时间...

- gilleain

Answer 5

一个不同的递归解决方案，只将结果添加到列表中。

static List<List<String>> substrings(String input) {
    List<List<String>> result = new ArrayList<>();
    if (input.length() == 1) {
        result.add(Arrays.asList(new String[]{input}));
    }
    else {
        //iterate j, ja, jav, jav
        for (int i = 0; i < input.length()-1; i++ ) {
            String root = input.substring(0,i+1);
            String leaf = input.substring(i+1);
            for( List<String> strings: substrings(leaf) ) {
                ArrayList<String> current = new ArrayList<String>();
                current.add(root);
                current.addAll(strings);
                result.add(current);
            }
        }
        //adds the whole string as one of the leaves (ie. java, ava, va, a)
        result.add(Arrays.asList(new String[]{input}));
    }
    return result;
}

- levrach

Answer 6

这个问题可以通过这段代码解决。

public static List<String> subsets(String s) {
if(Objects.isNull(s) || s.length() ==0){
    return Collections.emptyList();
}
int length = s.length();
List<String> result = new ArrayList<>();

for (int i = 0; i < length; i++) { // Group loop
    String substring = "";
    for (int j = 0; j < length; j++) { //
        if (i + j > length - 1) {
            substring = s.substring(j) + s.substring(0, ((i + j) - length) + 1);
        } else {
            substring = s.substring(j, j + i + 1);
        }
        result.add(substring);
    }
}
return result;}

输出

[a, b, c, d, ab, bc, cd, da, abc, bcd, cda, dab, abcd, bcda, cdab, dabc]

- Jatin Patel

Answer 7

您可以使用以下公式获取计数。

print(2**(len("ABCD")-1))

这里我使用ABCD作为我的输入字符串。

- Debayan