-4

我需要代码（或以下问题的代码片段或有关如何解决的提示）：

通过从s中删除一个或多个字符得到字符串s的子序列。字符串的子序列集s = abc是a, ab, ac, abc, b, bc, c,和空字符串（它是所有字符串的子序列）。

查找 s 的所有可能子序列并按字典顺序打印它们。

这就是我想出来的，但它不起作用：

TreeSet<String> ls = new TreeSet<>();

    for(int i=0;i<s.length();i++)
    {

        for(int j=i;j<s.length();j++)
        {
            StringBuffer sb = new StringBuffer();

            for(int k=i;k<j+1;k++)
            {
                sb.append(s.charAt(k));
            }

            ls.add(sb.toString());
        }

    }




    return ls.toArray(new String[ls.size()]);

结果：

TestCase : abc

输出： a ab abc b bc c

预期输出：a ab abc ac b bc c

4

1 回答 1

0

您的代码会查找substrings，它们是来自原始字符串的连续字符序列。但是，"ac"取自输入字符串的非连续字符，并且您不会使用您的方法获得该输出。

需要注意的一点是，您的输入字符串有 3 个字符，有 8 个可能的输出（包括空字符串）和 2 3 = 8。这应该表明您需要 3 个布尔值的所有 8 种可能组合，其中每个布尔值可以是true或false。然后，每个布尔值将对应于输入字符串的一个字符，这true意味着输入字符串中的字符在输出中，并且false意味着它不在输出中。然后通过查看所有可能的真/假组合来生成 8 个输出字符串。您使用 a 对它们进行排序的代码TreeSet似乎工作正常。

有几种可能的方法：

(1) 使用数组boolean并找出所有可能的组合。您可以从全部 false 开始，然后将第一个从 false 更改为 true，然后再将其更改回来，因为每当您将布尔值从 true 更改为 false 时，您也必须更改数组中的下一个布尔值。您可以尝试在纸上执行此操作，看看它是如何工作的。

(2) 认识到你的数组boolean是等价于一个整数的位，你可以通过在整数上反复加 1 来得到所有可能的位组合。然后，您将使用位运算来确定要包含输入字符串的哪些字符。

(3) 递归。如果您的输入字符串是，请递归"abc"查找 的所有子序列。"bc"对于 的每个子序列S，将是 的一个子序列"bc"，并且将是另一个。S"abc""a" + S

于 2016-08-29T03:09:15.263 回答