用包含重复字符的字符串生成所有不重复的子序列

Question

我正试图解决一个问题，我给了一个字符串重复字符在它，我应该生成所有唯一的子序列。

我现在如何生成所有子序列忽略重复部分或假设没有重复字符:(p代表进程，数据用于从进程中添加字符)

public static ArrayList generate(String process,String data){
if(data.isEmpty()){
ArrayList <String> temp = new ArrayList<>();
temp.add(process);
return temp;
}
ArrayList <String> left = new ArrayList<>();
ArrayList <String> right = new ArrayList<>();
left = generate(process+data.charAt(0),data.substring(1));
right = generate(process,data.substring(1));
left.addAll(right);
return left;
}

我不知道如何为非重复子序列做到这一点。我试图检查每个基本条件，如果我们已经在数组列表中添加了该字符串，但它仍然在这段代码中给我重复的答案:(up与上述代码中的数据相同未处理，p被处理或字符串最初从main传递)

public static ArrayList<String> generateNonDuplicate(String up, String p,ArrayList <String> current){
if(up.isEmpty()){
if(current.contains(p)){
return new ArrayList<>();
}
ArrayList <String> temp = new ArrayList<>();
temp.add(p);
return temp;
}
ArrayList <String> left = new ArrayList<>();
ArrayList <String> right = new ArrayList<>();        
left=generateNonDuplicate(up.substring(1), p+up.charAt(0), left);
right=generateNonDuplicate(up.substring(1), p, right);

left.addAll(right);
return left;
}

我该怎么做?

Answer 1

您可以通过简单的Google搜索得到它。这是来自GeeksforGeeks的一个天真的解决方案。在此链接找到更多解决方案:https://www.geeksforgeeks.org/count-distinct-subsequences/

// java program to print distinct
// subsequences of a given string
import java.io.*;
import java.lang.Math;
import java.util.*;
class GFG {
// Function for generating the subsequences
public static void subsequences(Set<String> sn,
char[] s, char[] op,
int i, int j, int n)
{
// Base Case
if (i == n) {
op[j] = '';
// Insert each generated
// subsequence into the set
sn.add(String.valueOf(op));
return;
}
// Recursive Case
else {
// When a particular character is taken
op[j] = s[i];
subsequences(sn, s, op, i + 1, j + 1, n);
// When a particular character isn't taken
subsequences(sn, s, op, i + 1, j, n);
return;
}
}
public static void main(String[] args)
{
char[] str = { 'g', 'g', 'g' };
int m = str.length;
int n = (int)Math.pow(2, m) + 1;
// Create an empty set to store the subsequences
Set<String> sn = new HashSet<String>();
// Output array for storing
// the generating subsequences
// in each call
char[] op = new char[m + 1]; // extra one for having
//  at the end
// Function Call
subsequences(sn, str, op, 0, 0, m);
// Output will be the number
// of elements in the set
System.out.println(sn.size());
sn.clear();
// This code is contributed by Aditya Sharma
}
}

Answer 2

再试一次。我无法解决你的解决方案，但如果你想用类似的方法给出两个解决方案:

1. 使用原始解决方案，并在最后删除重复项。您可以通过将解决方案放到一个集合中来实现:

   HashSet a = new HashSet<>(generate("， "aabc"));

结果:

[aa, , ab, a, bc, aac, ac, b, aab, abc, c, aabc]

如果你真的想使用复杂度为0 (2^N)的递归解决方案，下面是来自GFG的类似解决方案:

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG{

// Function to generate all distinct
// subsequences of the array using backtracking
public static void backtrack(ArrayList<Integer> nums,
int start,
ArrayList<Integer> curr_set)
{
System.out.print(curr_set + " ");
for(int i = start; i < nums.size(); i++)
{

// If the current element is repeating
if (i > start &&
nums.get(i) == nums.get(i - 1))
{
continue;
}
// Include current element
// into the subsequence
curr_set.add(nums.get(i));
// Proceed to the remaining array
// to generate subsequences
// including current array element
backtrack(nums, i + 1, curr_set);
// Remove current element
// from the subsequence
curr_set.remove(curr_set.size() - 1);
}
}
// Function to sort the array and generate
// subsequences using Backtracking
public static void AllSubsets(ArrayList<Integer> nums)
{
// Stores the current
// subsequence
ArrayList<Integer> curr_set = new ArrayList<>();
// Sort the vector
Collections.sort(nums);
// Backtrack function to
// generate subsequences
backtrack(nums, 0, curr_set);
}
// Driver Code
public static void main(String[] args)
{
ArrayList<Integer> v = new ArrayList<>();
v.add(1);
v.add(2);
v.add(2);

// Function call
AllSubsets(v);
}
}
// This code is contributed by hemanthswarna1506