给定一个字符串，如何生成所有可能的子字符串阵列，其中每个子字符串包含不超过n，但不少于m chars

Question

我有一个字符串str和两个正整数M和N，其中M可以小于或等于N。我想要的是拆分字符串，以便每个部分包含不超过N字符，但不小于M chars（假设字符串的长度大于M；如果不大于N，我们可以假设N等于字符串的长度）。例如，如果M=1，N=3和我的字符串是"aabcde"，则结果应为

var str = "aabcde";
var result = [
["a", "a", "b", "cde"],
["a", "ab", "cde"],
["aa", "b", "cde"],
//...
["aab", "cde"],
["aab", "cd", "e"],
["aab", "c", "de"],
["aab", "c", "d", "e"]  
]

避免不必要的中间子阵列解决此问题的有效方法是什么？我不想生成所有可能的组合，然后删除每个子阵列，如果它包含至少一个具有无法接受的长度的子字符串。有其他方法，没有不必要的计算？

Answer 1

这有效地归结为生成限制性整数组成，其中两个值介于两个值M和N之间。递归生成此类组成是一个简单的问题。

我还注意到您的"aabcde", M=1, N=3"示例，您的数组长度均小于或等于4的长度，因此我还提供了一个可选参数，以限制每个组合中的零件数量。

function* restrictedCompositions(n, a, b, k = n) {
    if (!(0 < a && a <= b && b <= n && 0 < k && k <= n)) {
        throw "invalid arguments";
    }
    let C = [];
    function* recGen(m, r) {
        if (m == 0) {
            yield C; // client must copy if they wish to store value for later
        }
        else {
            let y = Math.min(b, m);
            let x = Math.max(a, m - y*(r - 1));
            for (let v = x; v <= y; v++) {
                C.push(v);
                yield* recGen(m - v, r - 1);
                C.pop();
            }
        }   
    }
    yield* recGen(n, k);
}
function* generateChoppedStrings(str, M, N, K = str.length) {
    for (let composition of restrictedCompositions(str.length, M, N, K)) {
        let chopped = [];
        let i = 0;
        for (let part of composition) {
            let j = i + part;
            chopped.push(str.slice(i, j));
            i = j;
        }
        yield chopped;
    }
}
function chopString(str, M, N, K = str.length) {
    for (let chopped of generateChoppedStrings(str, M, N, K)) {
        console.log(chopped);
    }
}
chopString("aabcde", 1, 3, 4);

输出：

["a", "a", "b", "cde"]
["a", "a", "bc", "de"]
["a", "a", "bcd", "e"]
["a", "ab", "c", "de"]
["a", "ab", "cd", "e"]
["a", "ab", "cde"]
["a", "abc", "d", "e"]
["a", "abc", "de"]
["aa", "b", "c", "de"]
["aa", "b", "cd", "e"]
["aa", "b", "cde"]
["aa", "bc", "d", "e"]
["aa", "bc", "de"]
["aa", "bcd", "e"]
["aab", "c", "d", "e"]
["aab", "c", "de"]
["aab", "cd", "e"]
["aab", "cde"]

Answer 2

您可以使用递归生成所有可能的数组。获取所有可能的启动子字符串（长度为m..n），并在其余的字符串中调用下一个递归级别。

这种方法不会产生过多的（不良）子阵列（但可以在某些时候从字符串尾部产生相同的集合）

请注意，您可以使用子字符串和整数分割位置来工作，并在递归的最后一步中进行真实的子字符串。

简单的delphi示例：

procedure SplitStr(s, Reslt: string; LMin, LMax: Integer);
var
  i, Len: Integer;
  left, right: string;
begin
  Len := Length(s);
  if Len = 0 then
    Memo1.Lines.Add(Reslt)
  else
    for i := LMin to Min(LMax, Len) do begin
      left := LeftStr(s, i);
      right := RightStr(s, Len - i);
      SplitStr(right, Reslt + left + '| ' , LMin, LMax);
    end;
end;
begin
  SplitStr('aabcde', '', 1, 3);

输出

a| a| b| c| d| e| 
a| a| b| c| de| 
a| a| b| cd| e| 
a| a| b| cde| 
a| a| bc| d| e| 
a| a| bc| de| 
a| a| bcd| e| 
a| ab| c| d| e| 
a| ab| c| de| 
a| ab| cd| e| 
a| ab| cde| 
a| abc| d| e| 
a| abc| de| 
aa| b| c| d| e| 
aa| b| c| de| 
aa| b| cd| e| 
aa| b| cde| 
aa| bc| d| e| 
aa| bc| de| 
aa| bcd| e| 
aab| c| d| e| 
aab| c| de| 
aab| cd| e| 
aab| cde|