查找加起来等于给定字符串的所有子字符串组合
Find all the combination of substrings that add up to the given string
我正在尝试创建一个数据结构来保存所有可能的子字符串组合,这些组合加起来就是原始字符串。例如,如果字符串是 "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);
现在我正在尝试构建一个仅包含有效子字符串的结构。但这并不容易。我在一个非常丑陋的代码的迷雾中,摆弄着索引,并且没有完成的地方,很可能完全走错了路。有什么提示吗?
这是一种方法:
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]
这似乎是找到字符串长度的compositions,并使用这些组合来制作子字符串的问题。所以一个数n有2^n-1个组合,对于长字符串可能会有点耗时...
可能有人想要另一种非递归且不占用内存来保存列表的解决方案:
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]]
它只是根据其索引计算出下一个组合。
为了防止有人在 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')
只是添加到列表结果的不同递归解决方案
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;
}
我正在尝试创建一个数据结构来保存所有可能的子字符串组合,这些组合加起来就是原始字符串。例如,如果字符串是 "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);
现在我正在尝试构建一个仅包含有效子字符串的结构。但这并不容易。我在一个非常丑陋的代码的迷雾中,摆弄着索引,并且没有完成的地方,很可能完全走错了路。有什么提示吗?
这是一种方法:
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]
这似乎是找到字符串长度的compositions,并使用这些组合来制作子字符串的问题。所以一个数n有2^n-1个组合,对于长字符串可能会有点耗时...
可能有人想要另一种非递归且不占用内存来保存列表的解决方案:
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]]
它只是根据其索引计算出下一个组合。
为了防止有人在 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')
只是添加到列表结果的不同递归解决方案
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;
}