如何查找字符串的所有子词

Question

我正在尝试了解如何找到给定字符串的所有可能组合（子字符串）。我想到了一个有效的算法，它基本上是这样的：

示例："abc"

删除 none - 将 "abc" 添加到输出
删除第一个字符 ("bc") - 添加到输出，然后第二个 ("ac") - 添加到输出，然后删除第三个 ("ab") - 添加到输出。
删除 2 个字符（"a"、"b"、"c"）并添加到输出

现在，我不知道我将如何写这篇文章，所以我寻求一点帮助，没有什么高级的，因为这是我的硬件，我想自己学习和做。更具体地说，我想知道如何在不更改输入的情况下从中间删除一个字符。

此外，"cb" 对我来说不是子词，因为所有子词都需要按照它们在原始字符串中显示的顺序排列。

Answer 1

我会做一个递归函数。它看起来像这样

这不是可编译的 java 代码。它只是概述了一个算法

List<String> GetSubwords(String str)
{
    if(str.length == 1)
        return str; 

    List<String> result = new List<String>();
    FirstChar = str[0];

    // the portion of the string after the first character
    var smallString = str.Substring(1, str.length-1);
    List<String> smallerSubWords = GetSubwords(smallString);

    result.add(FirstChar.ToString())
    foreach(subword in smallerSubwords)
    {
        result.add(subword);
        result.add(firstChar + subword);
    }
    return result;
}

这本质上是获取一个字符串，比如 "ABCD"，删除 "A"，然后获取 "BCD" 和 returns 的所有子词的列表这些列表，除了那些在前面加上'A'的列表

Answer 2

我已经在 Iterator<T> 中实现了它，这样可以延迟生成内容。

import java.math.BigInteger;
import java.util.Iterator;

public class SubstringIterator implements Iterator<String> {

    String s;
    BigInteger cur = BigInteger.ZERO;
    BigInteger max;

    public SubstringIterator(String s) {
        this.s = s;
        max = BigInteger.ONE.shiftLeft(s.length()).subtract(BigInteger.ONE);
    }

    @Override
    public boolean hasNext() {
        return cur.compareTo(max) < 0;
    }

    @Override
    public String next() {
        cur = cur.add(BigInteger.ONE);
        StringBuilder sb = new StringBuilder();
        for(int i = 0x00; i < s.length(); i++) {
            if(cur.testBit(i)) {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("This is not a collection iterator");
    }



}

代码的工作原理如下：您需要声明一个位数组：一个具有任意位数的数组。现在我们在这里使用 BigInteger 因为这很方便，但是您可以使用任何等效的数据结构。

位数组维护一个位列表。当第i位为1时，表示对应的字符应该在要生成的字符串中，所以如果字符串为foobar且状态是 011011，结果将是：

foobar
011011
 oo ar

因此ooar。基于位数组生成字符串的过程由以下给出：

StringBuilder sb = new StringBuilder();
for(int i = 0x00; i < s.length(); i++) {
    if(cur.testBit(i)) {
        sb.append(s.charAt(i));
    }
}
return sb.toString();

现在唯一缺少的是迭代具有该长度的位数组集。为此，BigInteger 提供的方法很有用。这将执行二进制增量。但是，您可以使用 Gray counter。在那种情况下，输出的顺序会有点不同，但这不是主要问题。

所以我们设置 current 来表示状态。最初状态是 00000...000，因此是空字符串。但是我们不需要发出那种状态。

在 hasNext 方法中，我们检查 Iterator<T> 是否已经到达可能性的末尾。这是状态为11111....111时。因此，我们将最大值存储在 max 中，这是 n 倍 1 和 n 字符串的长度。

最后next方法只需要增加状态并计算结果。

现在你当然可以用结果生成一个数组。但总的来说 Iterator<T> 更好。迭代器不会显式存储所有值。所以内存使用量（几乎）是恒定的，而数组会导致指数内存使用量。

此外，它还可以节省 CPU 的使用量，因为并不总是需要计算所有值。假设您正在查看 foo 是否是一个成员，您可以从生成 "foo" 的那一刻起停止搜索，而首先构建整个数组可能会更昂贵。

查看在线演示 here。

如果空串也被认为是子串替换：

BigInteger cur = BigInteger.ZERO;

由

BigInteger cur = BigInteger.ONE.negate();

Answer 3

这是一个简单的 python 递归版本，java 中的翻译可能会很冗长，但非常简单：

def subs(s):
    if len(s) == 0:
        return ['']
    return [pref + sb for sb in subs(s[1:]) for pref in ('', s[0])]

print subs('ABC')

Answer 4

这是一个简单的算法。假设字符串的长度为 n。生成从 0 到 2^n-1 的所有数字。对于每个这样的数字，从左到右扫描其二进制表示，如果第 i 个位设置为 1，则将第 i 个字符写入输出。

这是 C++ 示例，您可以将其翻译成 java:

char s[] = "abc";
for(int i = 0; i < 1 << 3; i++)
{   for(int j = 0; j < 32; j++)
    {   if((1 << j) & i)
            printf("%c", s[j]);
    }
    puts("");
}

Answer 5

考虑一下：您必须找到所有以第一个字符开头的子词，然后是第二个字符，然后是第三个...等等。

这可以写成一个递归算法，有两个参数：

"prefix"
前缀之后的子词

在第一次迭代中，前缀将是一个空字符串，您将逐渐用子词填充它并打印一个字符。

我可以向您展示其工作原理的最简单方法是代码片段：

public void printAllSubWords(String prefix, String subword) {
    for(int i = 0; i < subword.length(); i++) {
        System.out.println(prefix + subword.charAt(i));
        printAllSubWords(prefix + subword.charAt(i), 
                         subword.substring(i + 1, subword.length()));
    }
}

这是如何工作的？

首先，考虑一个长度为2的字符串：

printAllSubWords("", "ab");

执行顺序是这样的：

当i = 0:

System.out.println(prefix + subword.charAt(i)); 会这样计算：
System.out.println("" + "ab".charAt(0)); 并将打印 a
那么调用
printAllSubWords(prefix + subword.charAt(i), subword.substring(i + 1, subword.length()));就会是
printAllSubWords("" + 'a', "ab".substring(0 + 1, "ab".length()));，也就是：
printAllSubWords("a", "b");
现在，在第二遍中，System.out.println(prefix + subword.charAt(i)); 将被这样计算：
System.out.println("a" + "b".charAt(0)); 并将打印 ab
那么，还是在这第二遍中，printAllSubWords(prefix + subword.charAt(i), subword.substring(i + 1, subword.length()));将是
printAllSubWords("a" + 'b', "b".substring(0 + 1, "ab".length()));，也就是：
printAllSubWords("ab", "");
在第三遍中，for不会被执行，因为这个新的子字（""）的长度为零，所以我们return到最顶层打电话。

当i = 1:

System.out.println(prefix + subword.charAt(i)); 会这样计算：
System.out.println("" + "ab".charAt(1)); 并将打印 b
那么调用
printAllSubWords(prefix + subword.charAt(i), subword.substring(i + 1, subword.length()));就会是
printAllSubWords("" + 'b', "b".substring(0 + 1, "ab".length()));，也就是：
printAllSubWords("b", "");
在这个新的第二遍中，for不会被执行，因为这个新的子词（""）的长度为零，所以我们return到顶部-大多数调用，这将结束执行。

试着写出一个三四个字符的单词的执行顺序，看看会发生什么。

希望对您有所帮助。

在您的评论中，您说您想将子词存储在一个数组中（并且您非常具体：您不需要列表，而是一个简单的数组）。这是可能的，但它有一些问题。

您需要预先知道数组需要多少条目。由于无法调整数组的大小，因此您需要在事情开始之前进行计算。

老实说，我会建议您使用 List（具体来说，ArrayList），但让我们看看是否可以计算数组的长度。

Word lenght | Number of subwords
------------+-------------------
  1         |   1
  2         |   3
  3         |   7
  4         |   15
  5         |   31

This question and its accepted answer 提示了长度为 n 的单词中有多少个子词。我留给你自己弄清楚（提示：答案的最后一部分是子序列数量的关键，但它包括 empty 子序列）。

一个可能的解决方案是：

创建一个整型静态变量（一个 class 变量）来保存您正在执行的迭代。该数字从零开始，每次 print/store 子词
在同一个 class 中，编写一个创建适当大小数组的方法。
修改上述方法，除了前缀和子词之外，还接收这个新创建的数组。
用我在步骤 1 中提到的静态变量作为索引，将生成的子词存储到数组中的句子替换 System.out.println() 东西。
再次调用该函数时，请务必同时传递数组。

几个小时后我会回来写代码示例，但我希望你先尝试自己解决它（另外，上面的 link 给了我另一个想法解决这个不需要递归的问题的方法，我将在以后的编辑中包含它)

我之前告诉你的解决方案是这样的：

public class SubwordPrinter2
{
    private static int index;
    private static void generateSubwords(String prefix, String subword, String[] arr) {
        String s;
        for(int i = 0; i < subword.length(); i++) {
            s = prefix + subword.charAt(i);
            arr[index] = s;
            index++;
            generateSubwords(prefix + subword.charAt(i),
                                subword.substring(i + 1, subword.length()),
                                arr);
        }
    }

    public static void generateAllSubwords(String word) {
        index = 0;
        String[] subwords = new String[(int)Math.pow(2, word.length()) - 1];
        generateSubwords("", word, subwords);
        for(String s : subwords) {
            System.out.println(s);
        }
    }
}

另一种不用递归的解决方案

由于顺序很重要，您可以创建一个二进制标志序列，告诉您一个字符是否必须包含在子词中。像这样：

String: abc
Flags:  001
        010
        011
        100
        101
        110
        111

那些是二进制字符串。所以算法是：

对于1和(2^n) - 1之间的i（其中n是单词的长度）
1. 创建一个二进制字符串，左边用零填充，与单词的长度相同。
2. 对于二进制字符串中的每个 1，print/store 匹配字符。

代码：

public void createSubwords(String word) {
    // As you can see, your array must have (2^n) - 1 entries
    String[] subwords = new String[(int)Math.pow(2, word.length()) - 1];
    String bin;
    String fmt;
    String subword;
    for(int i = 1; i < Math.pow(2, word.length()); i++) {
        // fmt will be used to format the binary string so it is
        // left padded with zeros
        fmt = "%0" + word.length() + "d";
        // bin is the binary string
        bin = String.format(fmt, Long.parseLong(Integer.toBinaryString(i)));
        // Initialize the subword
        subword = "";
        // For each '1' in the binary string, add the matching character
        // to the subword
        for(int j = 0; j < bin.length(); j++) {
            if(bin.charAt(j) == '1')
                subword = subword + word.charAt(j);
        }
        // Store it in the array
        subwords[i - 1] = subword;
    }
    // Print each subword
    for(String s : subwords) {
        System.out.println(s);
    }
}

希望对您有所帮助

如何查找字符串的所有子词

how to find all subwords of a string

java

string

substring