分解字符串算法

问题描述

问 题

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

例如，字符串 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"]
]

解决方案

先构出造字符串间隔位置对应的二进制，比如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;
}

这篇关于分解字符串算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！