给定一个字符串，求其不同子序列的计数。
null
例如：
Input : str = "gfg"Output : 7The seven distinct subsequences are "", "g", "f","gf", "fg", "gg" and "gfg" Input : str = "ggg"Output : 4The four distinct subsequences are "", "g", "gg"and "ggg"
如果输入字符串的所有字符都是不同的，那么计算不同子序列的问题很容易。计数等于 N C 0 + N C 1. + N C 2. + … N C N = 2 N . 当输入字符串中可能存在重复时，如何计算不同的子序列？ 一个简单的解决方案是在一个包含重复项的字符串中计算不同的子序列，即生成所有子序列。对于每个子序列，如果它不存在，则将其存储在哈希表中。这个解决方案的时间复杂度是指数的，需要指数级的额外空间。
方法1（天真的方法）：使用集合（无动态规划）
方法： 生成给定字符串的所有可能子序列。字符串的子序列可以以下列方式生成： （a） 包括一个特定的元素（比如i th )并递归调用输入字符串其余部分的函数。这将导致字符串的子序列具有i th 性格 b） 排除特定元素（例如i th )并递归调用该函数以获取输入字符串的其余部分。它包含所有没有i的子序列 th 性格 生成子序列后，在函数的基本情况下，我们将生成的子序列插入无序集中。无序集是一种数据结构，以无序的方式存储不同的元素。通过这种方式，我们在集合中插入所有生成的子序列，并打印集合的大小作为答案，因为最后，集合将只包含不同的子序列。
C++
// C++ program to print distinct // subsequences of a given string #include <bits/stdc++.h> using namespace std; // Create an empty set to store the subsequences unordered_set<string> sn; // Function for generating the subsequences void subsequences( char s[], char op[], int i, int j) { // Base Case if (s[i] == ' ' ) { op[j] = ' ' ; // Insert each generated // subsequence into the set sn.insert(op); return ; } // Recursive Case else { // When a particular character is taken op[j] = s[i]; subsequences(s, op, i + 1, j + 1); // When a particular character isn't taken subsequences(s, op, i + 1, j); return ; } } // Driver Code int main() { char str[] = "ggg" ; int m = sizeof (str) / sizeof ( char ); int n = pow (2, m) + 1; // Output array for storing // the generating subsequences // in each call char op[m+1]; //extra one for having at the end // Function Call subsequences(str, op, 0, 0); // Output will be the number // of elements in the set cout << sn.size(); sn.clear(); return 0; // This code is contributed by Kishan Mishra } |
Python3
# Python3 program to print # distinct subsequences of # a given string import math # Create an empty set # to store the subsequences sn = [] global m m = 0 # Function for generating # the subsequences def subsequences(s, op, i, j): # Base Case if (i = = m): op[j] = None temp = "".join([i for i in op if i]) # Insert each generated # subsequence into the set sn.append(temp) return # Recursive Case else : # When a particular # character is taken op[j] = s[i] subsequences(s, op, i + 1 , j + 1 ) # When a particular # character isn't taken subsequences(s, op, i + 1 , j) return # Driver Code str = "ggg" m = len ( str ) n = int (math. pow ( 2 , m) + 1 ) # Output array for storing # the generating subsequences # in each call op = [ None for i in range (n)] # Function Call subsequences( str , op, 0 , 0 ) # Output will be the number # of elements in the set print ( len ( set (sn))) # This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program to print distinct // subsequences of a given string // Create an empty set to store the subsequences let sn = new Set(); let m = 0; // Function for generating the subsequences function subsequences(s, op, i, j) { // Base Case if (i == m) { op[j] = ' ' ; // Insert each generated // subsequence into the set sn.add(op.join( "" )); return ; } // Recursive Case else { // When a particular character is taken op[j] = s[i]; subsequences(s, op, i + 1, j + 1); // When a particular character isn't taken subsequences(s, op, i + 1, j); return ; } } // Driver Code let str= "ggg" ; m = str.length; let n = Math.pow(2, m) + 1; // Output array for storing // the generating subsequences // in each call let op= new Array(n); // Function Call subsequences(str, op, 0, 0); // Output will be the number // of elements in the set document.write(sn.size); // This code is contributed by patel2127 </script> |
输出
4
时间复杂性 ：O（2^n） 腋窝间隙： O（n） 其中n是字符串的长度。
方法2（有效方法）：使用动态规划
有效的解决方案不需要生成子序列。
Let countSub(n) be count of subsequences of first n characters in input string. We canrecursively write it as below. countSub(n) = 2*Count(n-1) - RepetitionIf current character, i.e., str[n-1] of str hasnot appeared before, then Repetition = 0Else: Repetition = Count(m) Here m is index of previous occurrence of current character. We basically remove all counts ending with previous occurrence of current character.
这是怎么回事？ 如果没有重复，那么count变成n-1的count的两倍，因为我们通过在n-1长度的所有可能子序列的末尾添加当前字符来获得更多的子序列count（n-1）。 如果有重复，那么我们会发现所有不同的子序列都以上一个事件结束。可以通过递归调用前一次事件的索引来获得此计数。 由于上述递推具有重叠的子问题，我们可以使用动态规划来解决它。
下面是上述想法的实施。
C++
// C++ program to count number of distinct // subsequences of a given string. #include <bits/stdc++.h> using namespace std; const int MAX_CHAR = 256; // Returns count of distinct subsequences of str. int countSub(string str) { // Create an array to store index // of last vector< int > last(MAX_CHAR, -1); // Length of input string int n = str.length(); // dp[i] is going to store count of distinct // subsequences of length i. int dp[n + 1]; // Empty substring has only one subsequence dp[0] = 1; // Traverse through all lengths from 1 to n. for ( int i = 1; i <= n; i++) { // Number of subsequences with substring // str[0..i-1] dp[i] = 2 * dp[i - 1]; // If current character has appeared // before, then remove all subsequences // ending with previous occurrence. if (last[str[i - 1]] != -1) dp[i] = dp[i] - dp[last[str[i - 1]]]; // Mark occurrence of current character last[str[i - 1]] = (i - 1); } return dp[n]; } // Driver code int main() { cout << countSub( "gfg" ); return 0; } |
JAVA
// Java program to count number of distinct // subsequences of a given string. import java.util.ArrayList; import java.util.Arrays; public class Count_Subsequences { static final int MAX_CHAR = 256 ; // Returns count of distinct subsequences of str. static int countSub(String str) { // Create an array to store index // of last int [] last = new int [MAX_CHAR]; Arrays.fill(last, - 1 ); // Length of input string int n = str.length(); // dp[i] is going to store count of distinct // subsequences of length i. int [] dp = new int [n + 1 ]; // Empty substring has only one subsequence dp[ 0 ] = 1 ; // Traverse through all lengths from 1 to n. for ( int i = 1 ; i <= n; i++) { // Number of subsequences with substring // str[0..i-1] dp[i] = 2 * dp[i - 1 ]; // If current character has appeared // before, then remove all subsequences // ending with previous occurrence. if (last[( int )str.charAt(i - 1 )] != - 1 ) dp[i] = dp[i] - dp[last[( int )str.charAt(i - 1 )]]; // Mark occurrence of current character last[( int )str.charAt(i - 1 )] = (i - 1 ); } return dp[n]; } // Driver code public static void main(String args[]) { System.out.println(countSub( "gfg" )); } } // This code is contributed by Sumit Ghosh |
Python3
# Python3 program to count number of # distinct subsequences of a given string MAX_CHAR = 256 def countSub(ss): # create an array to store index of last last = [ - 1 for i in range (MAX_CHAR + 1 )] # length of input string n = len (ss) # dp[i] is going to store count of # discount subsequence of length of i dp = [ - 2 for i in range (n + 1 )] # empty substring has only # one subsequence dp[ 0 ] = 1 # Traverse through all lengths # from 1 to n for i in range ( 1 , n + 1 ): # number of subsequence with # substring str[0...i-1] dp[i] = 2 * dp[i - 1 ] # if current character has appeared # before, then remove all subsequences # ending with previous occurrence. if last[ ord (ss[i - 1 ])] ! = - 1 : dp[i] = dp[i] - dp[last[ ord (ss[i - 1 ])]] last[ ord (ss[i - 1 ])] = i - 1 return dp[n] # Driver code print (countSub( "gfg" )) # This code is contributed # by mohit kumar 29 |
C#
// C# program to count number of distinct // subsequences of a given string. using System; public class Count_Subsequences { static readonly int MAX_CHAR = 256; // Returns count of distinct subsequences of str. static int countSub(String str) { // Create an array to store index // of last int [] last = new int [MAX_CHAR]; for ( int i = 0; i < MAX_CHAR; i++) last[i] = -1; // Length of input string int n = str.Length; // dp[i] is going to store count of // distinct subsequences of length i. int [] dp = new int [n + 1]; // Empty substring has only one subsequence dp[0] = 1; // Traverse through all lengths from 1 to n. for ( int i = 1; i <= n; i++) { // Number of subsequences with substring // str[0..i-1] dp[i] = 2 * dp[i - 1]; // If current character has appeared // before, then remove all subsequences // ending with previous occurrence. if (last[( int )str[i - 1]] != -1) dp[i] = dp[i] - dp[last[( int )str[i - 1]]]; // Mark occurrence of current character last[( int )str[i - 1]] = (i - 1); } return dp[n]; } // Driver code public static void Main(String[] args) { Console.WriteLine(countSub( "gfg" )); } } // This code is contributed 29AjayKumar |
Javascript
<script> // Javascript program to count number of // distinct subsequences of a given string. let MAX_CHAR = 256; // Returns count of distinct subsequences // of str. function countSub(str) { // Create an array to store index // of last let last = new Array(MAX_CHAR); last.fill(-1); // Length of input string let n = str.length; // dp[i] is going to store count of distinct // subsequences of length i. let dp = new Array(n + 1); // Empty substring has only one subsequence dp[0] = 1; // Traverse through all lengths from 1 to n. for (let i = 1; i <= n; i++) { // Number of subsequences with substring // str[0..i-1] dp[i] = 2 * dp[i - 1]; // If current character has appeared // before, then remove all subsequences // ending with previous occurrence. if (last[str[i - 1].charCodeAt()] != -1) dp[i] = dp[i] - dp[last[str[i - 1].charCodeAt()]]; // Mark occurrence of current character last[str[i - 1].charCodeAt()] = (i - 1); } return dp[n]; } // Driver code document.write(countSub( "gfg" )); // This code is contributed by mukesh07 </script> |
输出
7
时间复杂性： O（n） 辅助空间： O（n）
方法3：没有额外的空间
假设我们有两个变量：`allCount`将不同子序列的总计数相加，以及`levelCount`存储以索引i结尾的子序列的计数。为了找到重复，我们将存储每个字符的最新levelCount。最后，我们将看到如何使用’levelCount’变量确定’allCount’。
以下是上述声明的陈述：
说s=“abab”
让我们用-1初始化映射中的所有字符串。此映射中的值表示此字符最后一次出现时结束的不同子序列的数量。
map={a:-1，b:-1}
最初我们也有
levelCount=0；
allCount=0；
现在遍历每个字符
第一次迭代“a”
以“a”结尾的不同子序列是：“a”。所以我们让levelCount=1，现在allCount也是1。 地图将像map[‘current_char`]=levelCount一样更新。
levelCount=1；allCount=1；map={a:1，b:-1}
第二次迭代“b”
以“b”结尾的不同子序列是“ab”、“b”。所以levelCount=2。
到目前为止，我们发现的子序列总数是3。allCount=3。
这里我们可以注意到，levelCount可以通过向allCount变量的最后一个值加1来确定
levelCount=allCount+1（levelCount=1+1=2）
在这种情况下，如果这是一个独特的字符，那么当前allCount也可以很容易地确定为
allCount=allCount+levelCount；（allCount=1+2=3）
我们还使用当前角色的levelCount更新地图。地图{a:1，b:2}
第三次迭代“a”
现在我们重复一遍。
以“a”结尾的不同子序列现在是“aa”、“ba”、“aba”、“a”。所以我们的levelCount现在是4：这是根据前面所说的allCount+1=3+1=4确定的。
如果这是一个不同的字符，allcount应该是7（allcount=allcount+levelCount=3+4），但我们必须删除重复，这就是映射。get（`a`）是1，所以现在allCount是7-1=6
这里需要注意的是，我们基本上删除了第一次迭代的结果，即重复的子序列“a”。这仅仅意味着我们可以形成以新成立的’a’结尾的子序列，而旧的’a’会形成相同的子序列，所以我们减去旧的子序列。
地图现在更新为a到{a:4，b:2}
如果重复计算，则所有计算更改如下：
allCount=allCount+levelCount–映射。获取（当前字符）；
allCount=3+4-1=6
第四次迭代“b”
再次重复。
以“b”结尾的子序列现在是“abb”、“bb”、“aab”、“bab”、“abab”、“ab”、“b”，其计数与levelCount=allCount+1=6+1=7相同。
allCount将=allCount+levelCount–映射。get（’b’）=6+7-2=11
不同子序列的总数为allCount。
如果还包括空字符串，那么我们的答案是allCount+1。
以下是上述方法的实施情况。
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Returns count of distinct // subsequences of str. int countSub(string s) { map< char , int > Map; // Iterate from 0 to s.length() for ( int i = 0; i < s.length(); i++) { Map[s[i]] = -1; } int allCount = 0; int levelCount = 0; // Iterate from 0 to s.length() for ( int i = 0; i < s.length(); i++) { char c = s[i]; // Check if i equal to 0 if (i == 0) { allCount = 1; Map = 1; levelCount = 1; continue ; } // Replace levelCount withe // allCount + 1 levelCount = allCount + 1; // If map is less than 0 if (Map < 0) { allCount = allCount + levelCount; } else { allCount = allCount + levelCount - Map; } Map = levelCount; } // Return answer return allCount; } // Driver code int main() { string list[] = { "abab" , "gfg" }; for (string s : list) { int cnt = countSub(s); int withEmptyString = cnt + 1; cout << "With empty string count for " << s << " is " << withEmptyString << endl; cout << "Without empty string count for " << s << " is " << cnt << endl; } return 0; } // This code is contributed by divyeshrabadiya07 |
JAVA
// Java Program for above approach import java.io.*; import java.util.*; class SubsequenceCount { // Returns count of distinct // subsequences of str. public static int countSub(String s) { HashMap<Character, Integer> map = new HashMap<Character, Integer>(); // Iterate from 0 to s.length() for ( int i = 0 ; i < s.length(); i++) { map.put(s.charAt(i), - 1 ); } int allCount = 0 ; int levelCount = 0 ; // Iterate from 0 to s.length() for ( int i= 0 ;i<s.length();i++) { char c = s.charAt(i); // Check if i equal to 0 if (i== 0 ) { allCount = 1 ; map.put(c, 1 ); levelCount = 1 ; continue ; } // Replace levelCount withe // allCount + 1 levelCount = allCount + 1 ; // If map is less than 0 if (map.get(c)< 0 ) { allCount = allCount + levelCount; } else { allCount = allCount + levelCount - map.get(c); } map.put(c,levelCount); } // Return answer return allCount; } // Driver Code public static void main(String[] args) { List<String> list = Arrays.asList( "abab" , "gfg" ); for (String s : list) { int cnt = countSub(s); int withEmptyString = cnt+ 1 ; System.out.println( "With empty string count for " + s + " is " + withEmptyString); System.out.println( "Without empty string count for " + s + " is " + cnt); } } } //Code is contributed by abhisht7 |
Python3
# Python3 program for above approach # Returns count of distinct # subsequences of str. def countSub(s): Map = {} # Iterate from 0 to length of s for i in range ( len (s)): Map [s[i]] = - 1 allCount = 0 levelCount = 0 # Iterate from 0 to length of s for i in range ( len (s)): c = s[i] # Check if i equal to 0 if (i = = 0 ): allCount = 1 Map = 1 levelCount = 1 continue # Replace levelCount withe # allCount + 1 levelCount = allCount + 1 # If map is less than 0 if ( Map < 0 ): allCount = allCount + levelCount else : allCount = allCount + levelCount - Map Map = levelCount # Return answer return allCount # Driver Code List = [ "abab" , "gfg" ] for s in List : cnt = countSub(s) withEmptyString = cnt + 1 print ( "With empty string count for" , s, "is" , withEmptyString) print ( "Without empty string count for" , s, "is" , cnt) # This code is contributed by rag2127 |
C#
// C# Program for above approach using System; using System.Collections.Generic; class GFG{ // Returns count of distinct // subsequences of str. public static int countSub(String s) { Dictionary< char , int > map = new Dictionary< char , int >(); // Iterate from 0 to s.length() for ( int i = 0; i < s.Length; i++) { if (!map.ContainsKey(s[i])) { map.Add(s[i], -1); } } int allCount = 0; int levelCount = 0; // Iterate from 0 to s.length() for ( int i = 0; i < s.Length; i++) { char c = s[i]; // Check if i equal to 0 if (i == 0) { allCount = 1; if (!map.ContainsKey(c)) { map.Add(c, 1); } else { map = 1; } levelCount = 1; continue ; } // Replace levelCount withe // allCount + 1 levelCount = allCount + 1; // If map is less than 0 if (map.ContainsKey(c)) { if (map < 0) { allCount = (allCount + levelCount); } else { allCount = (allCount + levelCount - map); } } if (!map.ContainsKey(c)) { map.Add(c, levelCount); } else { map = levelCount; } } // Return answer return allCount; } // Driver Code static void Main() { List< string > list = new List< string >(); list.Add( "abab" ); list.Add( "gfg" ); foreach ( string s in list) { int cnt = countSub(s); int withEmptyString = cnt + 1; Console.WriteLine( "With empty string count for " + s + " is " + withEmptyString); Console.WriteLine( "Without empty string count for " + s + " is " + cnt); } } } // This code is contributed by divyesh072019 |
Javascript
<script> // Javascript Program for above approach // Returns count of distinct // subsequences of str. function countSub(s) { let map = new Map(); // Iterate from 0 to s.length() for (let i = 0; i < s.length; i++) { map.set(s[i], -1); } let allCount = 0; let levelCount = 0; // Iterate from 0 to s.length() for (let i=0;i<s.length;i++) { let c = s[i]; // Check if i equal to 0 if (i==0) { allCount = 1; map.set(c,1); levelCount = 1; continue ; } // Replace levelCount withe // allCount + 1 levelCount = allCount + 1; // If map is less than 0 if (map.get(c)<0) { allCount = allCount + levelCount; } else { allCount = allCount + levelCount - map.get(c); } map.set(c,levelCount); } // Return answer return allCount; } // Driver Code let list=[ "abab" , "gfg" ]; for (let i=0;i<list.length;i++) { let cnt = countSub(list[i]); let withEmptyString = cnt+1; document.write( "With empty string count for " + list[i] + " is " + withEmptyString+ "<br>" ); document.write( "Without empty string count for " + list[i] + " is " + cnt+ "<br>" ); } // This code is contributed by unknown2108 </script> |
输出
With empty string count for abab is 12Without empty string count for abab is 11With empty string count for gfg is 7Without empty string count for gfg is 6
时间复杂性 ：O（n）
空间复杂性： O（1）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
