分割字符串的所有方法
All ways to partition a string
我正在尝试找到一种有效的算法来获得所有分割字符串的方法
例如对于给定的字符串 'abcd' =>
'a''bcd'
'a' 'b' 'cd'
'a' 'b' 'c' 'd'
'ab''cd'
'ab' 'c' 'd'
'abc''d'
'a', 'bc', 'd
任何语言都将不胜感激
提前致谢！
这是一种通过利用内置迭代器最大限度地减少开发人员时间的解决方案。对于答案本身并非不可行的问题大小，它应该相当快。
字符串的分区与潜在分割点的子集之间存在一对一的对应关系。如果字符串的长度是 n，那么有 n-1 个地方可以剪切字符串。一种直接的方法是遍历这样的子集，并且对于每个这样的子集，以这种方式对字符串进行切片。这是一个 Python 方法，它使用标准模块 itertools:
import itertools
def multiSlice(s,cutpoints):
k = len(cutpoints)
if k == 0:
return [s]
else:
multislices = [s[:cutpoints[0]]]
multislices.extend(s[cutpoints[i]:cutpoints[i+1]] for i in range(k-1))
multislices.append(s[cutpoints[k-1]:])
return multislices
def allPartitions(s):
n = len(s)
cuts = list(range(1,n))
for k in range(n):
for cutpoints in itertools.combinations(cuts,k):
yield multiSlice(s,cutpoints)
例如：
>>> parts = allPartitions('World')
>>> for p in parts: print(p)
['World']
['W', 'orld']
['Wo', 'rld']
['Wor', 'ld']
['Worl', 'd']
['W', 'o', 'rld']
['W', 'or', 'ld']
['W', 'orl', 'd']
['Wo', 'r', 'ld']
['Wo', 'rl', 'd']
['Wor', 'l', 'd']
['W', 'o', 'r', 'ld']
['W', 'o', 'rl', 'd']
['W', 'or', 'l', 'd']
['Wo', 'r', 'l', 'd']
['W', 'o', 'r', 'l', 'd']
请注意，此方法生成 ['World'] 作为 'World' 的分区。这对应于使用一组空的切割点进行切片。我认为这是一个特性而不是一个错误，因为分区的标准数学定义允许将一个集合分成一个部分。如果这对您的目的不利，则修复非常简单——只需遍历切割点的非空子集即可。就上述代码而言，此修复相当于向 allPartitions 添加两个字符：替换
for k in range(n):
来自
for k in range(1,n):
类似于以下内容（未经测试且可能存在错误 VB.NET 示例）
Function FindAllGroups(s As String) As List(Of List(Of String))
Dim ret As New List(Of List(Of String))
Dim l As New List(Of String)
l.Add(s) 'the whole string unbroken
ret.Add(l) 'first option we return is the whole unbroken string by itself
If s.Length > 1 Then
Dim tmp = FindAllGroups(s.Substring(1)) 'find all the groups for the rest of the string after the first character
For Each l2 in tmp
l = l2.ToList 'Copy it
l.Insert(s.SubString(0,1),0)'insert the first character from this string by itself before this combination for the rest of the string
ret.Add(l)
Next
For Each l2 in tmp
l = l2.ToList 'Copy it
l(0)= s.SubString(0,1) & l(0) 'insert the first character from this string as part of the first element in the list
ret.Add(l)
Next
End If
Return ret
End Function
这基本上是说我们可以将 'abcd' 拆分为
'a', 1st option for 'bcd' split
'a', 2nd option for 'bcd' split
...
+
1st option for 'bcd' split with the first element prepended with 'a'
2nd option for 'bcd' split with the first element prepended with 'a'
...
然后计算'bcd'，我们重复上面的过程，只是
'b', 1st option for 'cd' split
'b', 2nd option for 'cd' split
...
+
1st option for 'cd' split with the first element prepended with 'b'
2nd option for 'cd' split with the first element prepended with 'b'
...
等递归重复。
但是，这段代码在运行时并不是特别高效。你可以做的一件事来显着加快它的速度是在函数之外添加一个 Dictionary(Of String, List(Of List(Of String)) ，你可以在其中存储结果的缓存，如果项目存在于其中，你 return 从那里，如果没有，计算它并添加它。列表也可能不是最有效的，并且 ToList 函数可能不是最快的克隆方法。但是，我已经简化它使它更容易理解，也节省了我解决它的时间！
问题分析
每对相邻的字符之间，你可以决定是否剪切。对于一个大小为n的字符串，有n-1个位置可以切或不切，即有两种可能。因此，大小为 n 的字符串可以按 2n-1 方式进行分区。
输出由2n-1个分区组成，每个分区有n个字符加上分隔符。所以我们可以将输出大小描述为 f(n) = 2n-1 * n + s(n) 其中 s(n) ≥ 0 占分区分隔符和行分隔符。
因此仅由于输出大小，解决此问题的算法必须具有指数运行时间或更糟：Ω(2n) .
(0 ≤ c * 2n = ½ * 2n = 2n -1 ≤ 2n-1 * n ≤ f(n) 对于所有 n≥k正常数 c=½, k=1)
解决方案
我选择将分区表示为整数。 cutpoints中的每一位决定是否在字符i和i+1之间切分。要遍历所有可能的分区，我们只需要遍历 0 和 2^(n-1) - 1 之间的所有整数。
示例：对于长度为 4 的字符串，我们遍历 0 和 2^3 - 1 或 0 和 7 之间的所有整数或二进制：000 和 111.
# (python 2 or 3)
def all_partitions(string):
for cutpoints in range(1 << (len(string)-1)):
result = []
lastcut = 0
for i in range(len(string)-1):
if (1<<i) & cutpoints != 0:
result.append(string[lastcut:(i+1)])
lastcut = i+1
result.append(string[lastcut:])
yield result
for partition in all_partitions("abcd"):
print(partition)
内存使用：
我认为我的解决方案使用 O(n) 内存和 Python 3. 一次只生成一个分区，它被打印出来，不再被引用。如果您保留所有结果，这当然会改变，例如通过将它们存储在列表中。
在Python 2中将range替换为xrange，否则所有可能的cutpoints都将存储在一个列表中，因此需要指数级的内存。
JavaScript解法
// ES6 generator
function* all_partitions(string) {
for (var cutpoints = 0; cutpoints < (1 << (string.length - 1)); cutpoints++) {
var result = [];
var lastcut = 0;
for (var i = 0; i < string.length - 1; i++) {
if (((1 << i) & cutpoints) !== 0) {
result.push(string.slice(lastcut, i + 1));
lastcut = i + 1;
}
}
result.push(string.slice(lastcut));
yield result;
}
}
for (var partition of all_partitions("abcd")) {
console.log(partition);
}
使用 NodeJS v4.4.3 进行测试（免责声明：我之前没有使用过 NodeJS）。
GeeksforGeeks 为这个问题提供了一个解释清楚的解决方案：
对于字符串 abcd 会有 2^(n-1) 即 8 个分区。
(a)(b)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(a)(bcd)
(ab)(c)(d)
(ab)(cd)
(abc)(d)
(abcd)
解决的关键在于recursion打印所有排列。
维护两个参数——下一个要处理的字符的索引和到目前为止的输出字符串。我们从下一个要处理的字符的索引开始，将由未处理的字符串形成的子字符串附加到输出字符串并递归剩余的字符串，直到我们处理整个字符串。
// Java program to find all combinations of Non-
// overlapping substrings formed from given
// string
class GFG
{
// find all combinations of non-overlapping
// substrings formed by input string str
static void findCombinations(String str, int index,
String out)
{
if (index == str.length())
System.out.println(out);
for (int i = index; i < str.length(); i++)
// append substring formed by str[index,
// i] to output string
findCombinations(str, i + 1, out +
"(" + str.substring(index, i+1) + ")" );
}
// driver program
public static void main (String[] args)
{
// input string
String str = "abcd";
findCombinations(str, 0, "");
}
}
时间复杂度为 O(2^n)
这是文章的 link：http://www.geeksforgeeks.org/print-ways-break-string-bracket-form/
我只是想 post 为遇到这个问题的任何人提供一个简单的递归解决方案。可能不是最好的方法，但这对我来说更容易理解和实施。如果我错了，请指正。
def party(s:str, P:list, res:list) -> None :
"""Recursively generates all partitions of a given string"""
res.append(P+[s])
for i in range(1,len(s)):
party(s[i:],P+[s[:i]],res)
res = []
party("abcd",[],res)
print(res)
"""
[['abcd'], ['a', 'bcd'], ['a', 'b', 'cd'], ['a', 'b', 'c', 'd'],
['a', 'bc', 'd'], ['ab', 'cd'], ['ab', 'c', 'd'], ['abc', 'd']]
"""
它的工作原理如下：
给定一个字符串或它的一个子字符串，我们可以在它的每个字符之后拆分，创建两半。
说：“abc”可以划分为[“a”，“bc”]，[“ab”，“c”]
我们将第一部分保存在中间分区中 P 并且
在另一半上递归调用 party。
因为两半一起形成一个完整的分区，我们将其保存到 res。
示例：
最初：s = "abc" 是一个有效的分区，将其保存到 res.
recr call: s = "bc", P = ["a"] , 所以 P +[s]= ["a","bc"] 也是有效的，保存到 res .
继续拆分“bc”。
P = ["a","b"], s="c" 所以 P + [s] 也是有效的。等等..
recr call 3: s = "c", P = ["ab"], 所以P + [s] =["ab","c"]也是有效的，保存到res
工作：
tests = ["abc","abcd","a"]
for t in tests:
res = []
party(t,[],res)
print(f'{t} -> {res} \n')
"""Output
abc -> [['abc'], ['a', 'bc'], ['a', 'b', 'c'], ['ab', 'c']]
abcd -> [['abcd'], ['a', 'bcd'], ['a', 'b', 'cd'], ['a', 'b', 'c', 'd'],
['a', 'bc', 'd'], ['ab', 'cd'], ['ab', 'c', 'd'], ['abc', 'd']]
a -> [['a']]
"""
这是一个相当标准的深度优先搜索（回溯）问题。
void dfs(int startIndex, const string& s, vector<string>& tmp,
vector<vector<string>>& res){
if (startIndex == s.size()) {
res.push_back(tmp);
return;
}
for (int i = 1; startIndex + i <= s.size(); ++i) {
tmp.push_back(s.substr(startIndex, i));
dfs(startIndex + i, s, tmp, res);
tmp.pop_back();
}
}
int main()
{
vector<vector<string>> res;
vector<string> tmp;
string s = "abcd";
dfs(0, s, tmp, res);
}
其执行和结果请参考here。
#include <bits/stdc++.h>
using namespace std;
vector<string> ans;
string s;
void solve(int previouscut, int len)
{
if(previouscut == s.length()) // base case
{
for(auto str:ans)
cout << str << " " ;
cout << "\n";
return;
}
if(previouscut+len>s.length()) // boundary case
return;
//cut
ans.push_back(s.substr(previouscut,len));
solve(previouscut + len,1);
ans.pop_back(); //backtrack
// no cut
solve(previouscut, len+1);
}
int main()
{
cin >> s;
solve(0,1);
return 0;
}
我正在尝试找到一种有效的算法来获得所有分割字符串的方法
例如对于给定的字符串 'abcd' =>
'a''bcd'
'a' 'b' 'cd'
'a' 'b' 'c' 'd'
'ab''cd'
'ab' 'c' 'd'
'abc''d'
'a', 'bc', 'd
任何语言都将不胜感激
提前致谢！
这是一种通过利用内置迭代器最大限度地减少开发人员时间的解决方案。对于答案本身并非不可行的问题大小，它应该相当快。
字符串的分区与潜在分割点的子集之间存在一对一的对应关系。如果字符串的长度是 n，那么有 n-1 个地方可以剪切字符串。一种直接的方法是遍历这样的子集，并且对于每个这样的子集，以这种方式对字符串进行切片。这是一个 Python 方法，它使用标准模块 itertools:
import itertools
def multiSlice(s,cutpoints):
k = len(cutpoints)
if k == 0:
return [s]
else:
multislices = [s[:cutpoints[0]]]
multislices.extend(s[cutpoints[i]:cutpoints[i+1]] for i in range(k-1))
multislices.append(s[cutpoints[k-1]:])
return multislices
def allPartitions(s):
n = len(s)
cuts = list(range(1,n))
for k in range(n):
for cutpoints in itertools.combinations(cuts,k):
yield multiSlice(s,cutpoints)
例如：
>>> parts = allPartitions('World')
>>> for p in parts: print(p)
['World']
['W', 'orld']
['Wo', 'rld']
['Wor', 'ld']
['Worl', 'd']
['W', 'o', 'rld']
['W', 'or', 'ld']
['W', 'orl', 'd']
['Wo', 'r', 'ld']
['Wo', 'rl', 'd']
['Wor', 'l', 'd']
['W', 'o', 'r', 'ld']
['W', 'o', 'rl', 'd']
['W', 'or', 'l', 'd']
['Wo', 'r', 'l', 'd']
['W', 'o', 'r', 'l', 'd']
请注意，此方法生成 ['World'] 作为 'World' 的分区。这对应于使用一组空的切割点进行切片。我认为这是一个特性而不是一个错误，因为分区的标准数学定义允许将一个集合分成一个部分。如果这对您的目的不利，则修复非常简单——只需遍历切割点的非空子集即可。就上述代码而言，此修复相当于向 allPartitions 添加两个字符：替换
for k in range(n):
来自
for k in range(1,n):
类似于以下内容（未经测试且可能存在错误 VB.NET 示例）
Function FindAllGroups(s As String) As List(Of List(Of String))
Dim ret As New List(Of List(Of String))
Dim l As New List(Of String)
l.Add(s) 'the whole string unbroken
ret.Add(l) 'first option we return is the whole unbroken string by itself
If s.Length > 1 Then
Dim tmp = FindAllGroups(s.Substring(1)) 'find all the groups for the rest of the string after the first character
For Each l2 in tmp
l = l2.ToList 'Copy it
l.Insert(s.SubString(0,1),0)'insert the first character from this string by itself before this combination for the rest of the string
ret.Add(l)
Next
For Each l2 in tmp
l = l2.ToList 'Copy it
l(0)= s.SubString(0,1) & l(0) 'insert the first character from this string as part of the first element in the list
ret.Add(l)
Next
End If
Return ret
End Function
这基本上是说我们可以将 'abcd' 拆分为
'a', 1st option for 'bcd' split
'a', 2nd option for 'bcd' split
...
+
1st option for 'bcd' split with the first element prepended with 'a'
2nd option for 'bcd' split with the first element prepended with 'a'
...
然后计算'bcd'，我们重复上面的过程，只是
'b', 1st option for 'cd' split
'b', 2nd option for 'cd' split
...
+
1st option for 'cd' split with the first element prepended with 'b'
2nd option for 'cd' split with the first element prepended with 'b'
...
等递归重复。
但是，这段代码在运行时并不是特别高效。你可以做的一件事来显着加快它的速度是在函数之外添加一个 Dictionary(Of String, List(Of List(Of String)) ，你可以在其中存储结果的缓存，如果项目存在于其中，你 return 从那里，如果没有，计算它并添加它。列表也可能不是最有效的，并且 ToList 函数可能不是最快的克隆方法。但是，我已经简化它使它更容易理解，也节省了我解决它的时间！
问题分析
每对相邻的字符之间，你可以决定是否剪切。对于一个大小为n的字符串，有n-1个位置可以切或不切，即有两种可能。因此，大小为 n 的字符串可以按 2n-1 方式进行分区。
输出由2n-1个分区组成，每个分区有n个字符加上分隔符。所以我们可以将输出大小描述为 f(n) = 2n-1 * n + s(n) 其中 s(n) ≥ 0 占分区分隔符和行分隔符。
因此仅由于输出大小，解决此问题的算法必须具有指数运行时间或更糟：Ω(2n) .
(0 ≤ c * 2n = ½ * 2n = 2n -1 ≤ 2n-1 * n ≤ f(n) 对于所有 n≥k正常数 c=½, k=1)
解决方案
我选择将分区表示为整数。 cutpoints中的每一位决定是否在字符i和i+1之间切分。要遍历所有可能的分区，我们只需要遍历 0 和 2^(n-1) - 1 之间的所有整数。
示例：对于长度为 4 的字符串，我们遍历 0 和 2^3 - 1 或 0 和 7 之间的所有整数或二进制：000 和 111.
# (python 2 or 3)
def all_partitions(string):
for cutpoints in range(1 << (len(string)-1)):
result = []
lastcut = 0
for i in range(len(string)-1):
if (1<<i) & cutpoints != 0:
result.append(string[lastcut:(i+1)])
lastcut = i+1
result.append(string[lastcut:])
yield result
for partition in all_partitions("abcd"):
print(partition)
内存使用：
我认为我的解决方案使用 O(n) 内存和 Python 3. 一次只生成一个分区，它被打印出来，不再被引用。如果您保留所有结果，这当然会改变，例如通过将它们存储在列表中。
在Python 2中将range替换为xrange，否则所有可能的cutpoints都将存储在一个列表中，因此需要指数级的内存。
JavaScript解法
// ES6 generator
function* all_partitions(string) {
for (var cutpoints = 0; cutpoints < (1 << (string.length - 1)); cutpoints++) {
var result = [];
var lastcut = 0;
for (var i = 0; i < string.length - 1; i++) {
if (((1 << i) & cutpoints) !== 0) {
result.push(string.slice(lastcut, i + 1));
lastcut = i + 1;
}
}
result.push(string.slice(lastcut));
yield result;
}
}
for (var partition of all_partitions("abcd")) {
console.log(partition);
}
使用 NodeJS v4.4.3 进行测试（免责声明：我之前没有使用过 NodeJS）。
GeeksforGeeks 为这个问题提供了一个解释清楚的解决方案：
对于字符串 abcd 会有 2^(n-1) 即 8 个分区。
(a)(b)(c)(d)
(a)(b)(cd)
(a)(bc)(d)
(a)(bcd)
(ab)(c)(d)
(ab)(cd)
(abc)(d)
(abcd)
解决的关键在于recursion打印所有排列。
维护两个参数——下一个要处理的字符的索引和到目前为止的输出字符串。我们从下一个要处理的字符的索引开始，将由未处理的字符串形成的子字符串附加到输出字符串并递归剩余的字符串，直到我们处理整个字符串。
// Java program to find all combinations of Non-
// overlapping substrings formed from given
// string
class GFG
{
// find all combinations of non-overlapping
// substrings formed by input string str
static void findCombinations(String str, int index,
String out)
{
if (index == str.length())
System.out.println(out);
for (int i = index; i < str.length(); i++)
// append substring formed by str[index,
// i] to output string
findCombinations(str, i + 1, out +
"(" + str.substring(index, i+1) + ")" );
}
// driver program
public static void main (String[] args)
{
// input string
String str = "abcd";
findCombinations(str, 0, "");
}
}
时间复杂度为 O(2^n)
这是文章的 link：http://www.geeksforgeeks.org/print-ways-break-string-bracket-form/
我只是想 post 为遇到这个问题的任何人提供一个简单的递归解决方案。可能不是最好的方法，但这对我来说更容易理解和实施。如果我错了，请指正。
def party(s:str, P:list, res:list) -> None :
"""Recursively generates all partitions of a given string"""
res.append(P+[s])
for i in range(1,len(s)):
party(s[i:],P+[s[:i]],res)
res = []
party("abcd",[],res)
print(res)
"""
[['abcd'], ['a', 'bcd'], ['a', 'b', 'cd'], ['a', 'b', 'c', 'd'],
['a', 'bc', 'd'], ['ab', 'cd'], ['ab', 'c', 'd'], ['abc', 'd']]
"""
它的工作原理如下： 给定一个字符串或它的一个子字符串，我们可以在它的每个字符之后拆分，创建两半。 说：“abc”可以划分为[“a”，“bc”]，[“ab”，“c”]
我们将第一部分保存在中间分区中 P 并且
在另一半上递归调用 party。
因为两半一起形成一个完整的分区，我们将其保存到 res。
示例：
最初：s = "abc" 是一个有效的分区，将其保存到 res.
recr call: s = "bc", P = ["a"] , 所以 P +[s]= ["a","bc"] 也是有效的，保存到 res .
继续拆分“bc”。 P = ["a","b"], s="c" 所以 P + [s] 也是有效的。等等..
recr call 3: s = "c", P = ["ab"], 所以P + [s] =["ab","c"]也是有效的，保存到res
工作：
tests = ["abc","abcd","a"]
for t in tests:
res = []
party(t,[],res)
print(f'{t} -> {res} \n')
"""Output
abc -> [['abc'], ['a', 'bc'], ['a', 'b', 'c'], ['ab', 'c']]
abcd -> [['abcd'], ['a', 'bcd'], ['a', 'b', 'cd'], ['a', 'b', 'c', 'd'],
['a', 'bc', 'd'], ['ab', 'cd'], ['ab', 'c', 'd'], ['abc', 'd']]
a -> [['a']]
"""
这是一个相当标准的深度优先搜索（回溯）问题。
void dfs(int startIndex, const string& s, vector<string>& tmp,
vector<vector<string>>& res){
if (startIndex == s.size()) {
res.push_back(tmp);
return;
}
for (int i = 1; startIndex + i <= s.size(); ++i) {
tmp.push_back(s.substr(startIndex, i));
dfs(startIndex + i, s, tmp, res);
tmp.pop_back();
}
}
int main()
{
vector<vector<string>> res;
vector<string> tmp;
string s = "abcd";
dfs(0, s, tmp, res);
}
其执行和结果请参考here。
#include <bits/stdc++.h>
using namespace std;
vector<string> ans;
string s;
void solve(int previouscut, int len)
{
if(previouscut == s.length()) // base case
{
for(auto str:ans)
cout << str << " " ;
cout << "\n";
return;
}
if(previouscut+len>s.length()) // boundary case
return;
//cut
ans.push_back(s.substr(previouscut,len));
solve(previouscut + len,1);
ans.pop_back(); //backtrack
// no cut
solve(previouscut, len+1);
}
int main()
{
cin >> s;
solve(0,1);
return 0;
}