如何找到所有不同的组合作为一个字符串的字符的不同长度的单位

本文关键字：一个 字符串 单位 字符 何找 组合 | 更新日期: 2023-09-27 18:04:50

嗨，我想从给定字符串中找到所有不同的组合，而不是线性选择字符，而不会失去作为不同大小单位的序列。例子:

让我们说一个词"HAVING"

然后它可以有组合，如(空格分隔单个单位)

HA VI N G
HAV ING
H AV I N G
HAVIN G
H AVING
H AVIN G
HA VING
H AVI NG
....

像这样选择不同长度的单位。

谁能给一个原型代码或算法的想法。

谢谢,Kalyana

如何找到所有不同的组合作为一个字符串的字符的不同长度的单位

在大小为n的字符串中，您有n-1位置可以放置空格(=在每对连续字母之间)。因此，您有2^(n-1)选项，每个选项由具有n-1位的二进制数表示，例如，您的第一个示例将是01011。

这应该给你足够的信息开始(没有完整的解决方案;

简单递归解。两组是第一个字母和单词的其余部分。找出单词其余部分的所有组合。然后把第二个字母和第一个字母放在一起，找出单词其余部分的所有组合。重复，直到剩下的单词是1个字母。

这只是一个幂集，不是吗?对于字符串中两个字母之间的每个位置，有或没有空格。所以对于长度为6的字符串，有2的5次方种可能性。

一个简单的递归函数将列举所有的可能性。你需要帮助编写这样的函数还是你只是在寻找算法?

每个字母之间要么有分隔符，要么没有。所以递归遍历单词，尝试所有分隔符/非分隔符的组合。

function f( word )
    set = word[0] + f( substring(word, 1) )
    set += word[0] + " " + f( substring(word, 1) )
    return set;

我的解决方案
比如

void func(string s)
{  
  int len=s.length();
  if(len==0)
  return;
  for(int i=1;i<=len;i++)
  {
    for(int j=0;j<i;j++)
    cout<<s[j];
    cout<<" ";
    func(s[i]);
  }
  return;
}

递归。在java: 

public static List<List<String>> split (String str) {
    List<List<String>> res = new ArrayList<List<String>>();
    if (str == null) {
        return res;
    }
    for (int i = 0; i < str.length() - 1; i++) {
        for (List<String> list : split(str.substring(i + 1))) {
            List<String> tmpList = new ArrayList<String>();
            tmpList.add(str.substring(0, i + 1));
            for (String s : list) {
                tmpList.add(s);
            }
            res.add(tmpList);
        }
    }
    List<String> tmpList = new ArrayList<String>();
    tmpList.add(str);
    res.add(tmpList);
    return res;
}
public static void main(String[] args) {
    for (List<String> intermed : split("HAVING")) {
        for (String str : intermed) {
            System.out.print(str);
            System.out.print(" ");
        }
        System.out.println();
    }
}
相关文章：