分解字符串算法

Question

有什么方法把一个字符串分解成全部组成片段呢？

例如，字符串 abcde 可被分解为：

[
  ["a", "bcde"],
  ["ab", "cde"],
  ["abc", "de"],
  ["abcd", "e"],

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

  ["a", "b", "c", "de"],
  ["a", "b", "cd", "e"],
  ["a", "bc", "d", "e"],
  ["ab", "c", "d", "e"],

  ["a", "b", "c", "d", "e"]
]

Answer 1

先构出造字符串间隔位置对应的二进制，比如abc 对应11，然后从0计算到构造出来的二进制，当某个位置为1时，插入分隔符，每个数都根据分隔符切割即可。比如abc，二进制为11，为0时，字符串没有分隔符，数组为abc，当为01时，字符串为ab!c，可切割为ab和c，当为时，字符为a!bc，可切割为a和bc，当为11时，字符为a!b!c，可切割为a和b和c。
递归虽好，但是也不要滥用，层次深了效率会非常低。有人要算法，那我就贴个代码吧，大家看看就好~

// splitString.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>

using namespace std;

int splitString(char *str);

int _tmain(int argc, _TCHAR* argv[])
{
    char str[50] = { 0 };

    while (1) {
        cout << "Please input string: " << endl;
        cin >> str;
        splitString(str);
    }
    return 0;
}

//字符切割，最大长度32位
int splitString(char *str) {
    //计算字符串长度
    int len = strlen(str);

    //构建二进制
    int binary = 1 << (len - 1);
    
    char* curStr = new char[len];
    cout << "result:" << endl;
    for (int i = 0; i < binary; i++) {
        int n = i;
        int k = 0;
        int j = 0;

        memset(curStr, 0, sizeof(char) * len);
        while (n) {
            curStr[k++] = str[j++];
            //找到为1的位
            if (n % 2) {
                //输出结果，并重置数组
                cout << curStr << " ,";
                memset(curStr, 0, len);
                k = 0;
            }
            n /= 2;
        }

        //输出最后的数组
        cout << (&str[j]) << endl;

    }

    delete[] curStr;
    return 0;
}

Answer 2

可以看看这篇task，对你有点帮助
9_billion_names_of_God_the_integer
可以参考我的笔记

Answer 3

换个顺序应该就能看出规律了吧：

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

这是一个典型的动态规划分治问题。每次只考虑把字符串分成两个部分，然后递归求解即可，只不过在递归的时候需要用栈来记录路径。使用 C++ 实现如下：

#include <string>
#include <iostream>
#include <vector>
using namespace std;

void split(vector<string> &comb, string s) {
  if (s == "") {
    for (const auto &e : comb)
      cout << e << " ";
    cout << endl;
  }
  for (unsigned i = 1; i <= s.size(); ++i) {
    comb.push_back(s.substr(0, i));  // s 中 [0, i) 的部分
    split(comb, s.substr(i));        // s 中 [i, size) 的部分
    comb.pop_back();
  }
}

int main() {
  string s;
  cin >> s;

  vector<string> combination;  // 栈，记录字符串已经分好的部分
  split(combination, s);

  return 0;
}

如果需要排序，可以将输出的结果保存起来然后排序。

Answer 4

@Lzdnku 你的思路把问题转换的非常巧妙。我用 js 实现了

function dec2bin(dec) {
  return (dec >>> 0).toString(2);
}

function bin2dec(bin) {
  return parseInt(bin, 2);
}

function getMaxSplitDec(term) {
  var length = term.length - 1;
  var result = new Array(length).fill('1').join('');
  return bin2dec(result);
}

function getBits(dec) {
  var binString = dec2bin(dec);
  var result = [];
  for (var i = binString.length, bit = 1; i > 0; --i, ++bit) {
    var current = i - 1;
    if (binString.charAt(current) === '1') result.push(bit);
  }
  return result;
}

function reverseSplit(text, bits) {
  var splitBits = bits.map(function(reversePoint) {
    return text.length - reversePoint;
  }).sort();
  splitBits.unshift(0);
  var result = [];
  for (var i = 0; i < splitBits.length; ++i) {
    result.push(text.substring(splitBits[i], splitBits[i + 1]));
  }
  return result;
}

function getComposite(term) {
  var max = getMaxSplitDec(term);
  var result = [];
  for (var i = 0; i < max; ++i) {
    var current = i + 1;
    var bits = getBits(current);
    result.push(reverseSplit(term, bits));
  }
  return result;
}

// 实际调用
console.log(getComposite('abcde'));

好像比上面动态规划的要长很多？算了不管了

Answer 5

应该是递归实现