统计所有可能通过放置空格产生的字符串
原文:https://www . geeksforgeeks . org/count-所有可能的字符串-可以通过放置空格生成的字符串/
给定一个字符串 S ，任务是通过在字符串的任意一对相邻字符之间放置空格来计数所有可能生成的字符串。
示例:
输入:S = " AB " T3】输出:2 T6】解释:所有可能的字符串都是{“A B”、“AB”}。
输入: S = "ABC" 输出: 4 解释:所有可能的字符串为{“A BC”、“ABC”、“A BC”、“ABC”}
方法:假设字符串相邻字符对之间的空格为二进制位，可以解决这个问题。一般来说，如果字符串的长度是 L ，那么就有L–1的地方要用空格填充。
插图:
S = "ABCD" 空格的可能位置是:
- 在“甲”和“乙”之间
- 在“乙”和“丙”之间
- 在“C”和“D”之间
字符串长度= 4 空格的可能空格= 3 = 4–1 假设每个位置是一个二进制位，可能组合的总数为:
- 000->“ABCD”
- 001->“ABC D”
- 010->“AB 光盘”
- 011->“AB C D”
- 100 ->“一个 BCD”
- 101 ->《公元前一世纪》
- 110 ->“甲乙光盘”
- 111 ->《甲乙丙丁》
因此，对于长度为 4 的字符串，可以获得 8 个可能的字符串。 因此，字符串总数= 2L–1
下面是上述想法的实现:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
long long int countNumberOfStrings(string s)
{
// Length of the string
int length = s.length();
// Count of positions for spaces
int n = length - 1;
// Count of possible strings
long long int count = pow(2, n);
return count;
}
// Driver Code
int main()
{
string S = "ABCD";
cout << countNumberOfStrings(S);
return 0;
}
C
// C program to implement
// the above approach
#include <math.h>
#include <stdio.h>
#include <string.h>
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
long long int countNumberOfStrings(char* s)
{
// Length of the string
int length = strlen(s);
// Count of positions for spaces
int n = length - 1;
// Count of possible strings
long long int count = pow(2, n);
return count;
}
// Driver Code
int main()
{
char S[] = "ABCD";
printf("%lld", countNumberOfStrings(S));
return 0;
}
// This code is contributed by single__loop
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
static long countNumberOfStrings(String s)
{
// Count of positions for spaces
int n = s.length() - 1;
// Count of possible strings
long count = (long)(Math.pow(2, n));
return count;
}
// Driver Code
public static void main(String[] args)
{
String S = "ABCD";
System.out.println(countNumberOfStrings(S));
}
}
// This code is contributed by single__loop
Python 3
# Python3 program to implement
# the above approach
# Function to count the number of strings
# that can be generated by placing spaces
# between pair of adjacent characters
def countNumberOfStrings(s):
# Length of the string
length = len(s)
# Count of positions for spaces
n = length - 1
# Count of possible strings
count = 2 ** n
return count
# Driver Code
if __name__ == "__main__" :
S = "ABCD"
print(countNumberOfStrings(S))
# This code is contributed by AnkThon
C
// C# program to implement
// the above approach
using System;
class GFG{
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
static long countNumberOfStrings(String s)
{
// Count of positions for spaces
int n = s.Length - 1;
// Count of possible strings
long count = (long)(Math.Pow(2, n));
return count;
}
// Driver Code
public static void Main(String[] args)
{
string S = "ABCD";
Console.WriteLine(countNumberOfStrings(S));
}
}
// This code is contributed by AnkThon
java 描述语言
<script>
// JavaScript program for above approach
// Function to count the number of strings
// that can be generated by placing spaces
// between pair of adjacent characters
function countNumberOfStrings(s)
{
// Count of positions for spaces
let n = s.length - 1;
// Count of possible strings
let count = (Math.pow(2, n));
return count;
}
// Driver Code
let S = "ABCD";
document.write(countNumberOfStrings(S));
// This code is contributed by avijitmondal1998.
</script>
Output:
8
时间复杂度:*O(log(len–1))，其中 len 代表给定字符串的长度。 辅助空间:* O(1)
版权属于：月萌API www.moonapi.com，转载请注明出处
