Javascript 生成具有最大子串长度的最小子串集数

以下是一种使用递归的可能方法，但没有针对性能进行优化(例如，没有memoization):

function splits(s: string, maxLen: number, minInitLen: number = 1): string[][] {
  const ret: string[][] = s.length ? [] : [[]];
  for (let i = Math.min(maxLen, s.length); i >= minInitLen; i--) {
    for (const r of splits(s.slice(i), maxLen, maxLen + 1 - i)) {
      ret.push([s.slice(0, i), ...r]);
    }
  }
  return ret;
}

其思想是，splits()不仅包括要拆分的字符串s和子串的最大长度maxLen，而且还包括第一个子串的最小允许长度minInitLen.当您开始拆分字符串时，这个初始长度是1，但在递归中它可能更大.毕竟，让我们假设到目前为止，您已经将"abcdef"拆分为"a".现在需要拆分"bcdef"，但下一个子字符串的长度必须为3("bcd")，因为"b"将折叠为"ab","bc"将折叠为"abc".如果到目前为止已经将其拆分成"ab"个，那么下一个子字符串的长度必须至少为2("cd"或"cde")，因为"c"将折叠为"abc".相关的数学运算是，如果当前子串的长度为i，则下一个子串的长度必须至少为maxLen + 1 - i.

递归的基本情况是要求您拆分空字符串.在本例中，您希望返回[[]]；只有一种方法可以拆分空字符串.如果要拆分一个非空字符串，则需要迭代第一个子字符串的长度i，介于minInitLen和maxLen之间(当然，也不能超过s.length)，并计算递归结果splits(s.slice(i), maxLen, maxLen + 1 - i)，然后对于结果中的每组字符串，在其前面加上初始子字符串s.slice(0, i).

让我们看看它是否奏效:

console.log(splits("abcdef", 3))
// [["abc", "def"], ["ab", "cde", "f"], ["ab", "cd", "ef"], ["a", "bcd", "ef"]] 

console.log(splits("abcdefgh", 5))
// [["abcde", "fgh"], ["abcd", "efgh"], ["abc", "defgh"], ["ab", "cdefg", "h"], 
//  ["ab", "cdef", "gh"], ["a", "bcdef", "gh"]] 

它看起来不错，至少对于您的示例输入是这样的.我不确定是否存在边缘情况，或者性能是否成为大型字符串的问题(这可能在很大程度上取决于"大型"的含义).如果愿意的话，当然可以重构为使用函数式编程数组方法，而不是for个循环.但至少它起作用了.

Playground link to code个