Dada una string binaria y k, para verificar si contiene todas las permutaciones de longitud k o no.
Ejemplos:
Input : Binary string 11001
k : 2
Output : Yes
11001 contains all possibilities of
binary sequences with k = 2, 00, 01,
10, 11
Input : Binary string: 1001
k : 2
Output: No
1001 does not contain all possibilities of
binary sequences with k = 2. Here 11
sequence is missing
Método 1:
Explicación:
En este ejemplo, no se encuentra una secuencia binaria de longitud k, es 0110.
Entonces, todas las secuencias binarias con k=4 serán 2 4 =16. están siguiendo
0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111,
1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
Todo debe ser una substring de una string binaria dada y luego imprimir Sí de lo contrario No
Algoritmo
Tomando string binaria y el tamaño k. En la string binaria, verificamos que las secuencias binarias coincidan o no. La secuencia binaria está hecha de tamaño k, ya que sabemos que en binario usa 0 y 1 dígito, por lo que generar subconjuntos binarios totales es 2 k elementos. La idea principal detrás de esto es almacenar todos los valores binarios en la lista como una string y luego comparar la lista de todos los elementos con la string binaria dada como subconjunto. Si todo ocurre dentro de la string binaria, imprima «Sí», de lo contrario, imprima «No».
Java
// Java program to Check a binary string
// contains all permutations of length k.
import java.util.*;
public class Checkbinary {
// to check all Permutation in given String
public static boolean tocheck(String s, int k)
{
List<String> list = BinarySubsets(k);
// to check binary sequences are available
// in string or not
for (String b : list)
if (s.indexOf(b) == -1)
return false;
return true;
}
// to generate all binary subsets of given length k
public static List<String> BinarySubsets(int k)
{
// Declare the list as String
List<String> list = new ArrayList<>();
// to define the format of binary of
// given length k
String format = "%0" + k + "d";
// returns the string representation of the
// unsigned integer value represented by
// the argument in binary (base 2) using
// Integer.toBinaryString and convert it
// into integer using Integer.valueOf.
// Loop for 2<sup>k</sup> elements
for (int i = 0; i < Math.pow(2, k); i++)
{
// To add in the list all possible
// binary sequence of given length
list.add(String.format(format,
Integer.valueOf(Integer.toBinaryString(i))));
/* To Show all binary sequence of given
length k
System.out.println(String.format(format,
Integer.valueOf(Integer.toBinaryString(i))));*/
}
return list;
}
// drive main
public static void main(String[] args)
{
String str = "11001";
int num = 2;
if (tocheck(str, num))
System.out.println("Yes");
else
System.out.println("No");
}
}
Yes
Método 2:
Algoritmo
Tomando string binaria y el tamaño k. En la string binaria, verificamos que las secuencias binarias coincidan o no. La secuencia binaria está hecha de tamaño k, ya que sabemos que en binario usa 0 y 1 dígito, por lo que generar subconjuntos binarios totales es 2 k elementos. La idea principal detrás de esto es almacenar toda la substring de tamaño k de la string dada en el conjunto, es decir, almacenar la substring distinta de tamaño k. Si el tamaño del conjunto es igual a 2 k , escriba «SÍ», de lo contrario, escriba «NO».
C++14
// C++ Program to Check If a
// String Contains All Binary
// Codes of Size K
#include <bits/stdc++.h>
using namespace std;
#define int long long
bool hasAllcodes(string s, int k)
{
// Unordered map of type string
unordered_set<string> us;
for (int i = 0; i + k <= s.size(); i++)
{
us.insert(s.substr(i, k));
}
return us.size() == 1 << k;
}
// Driver Code
signed main()
{
string s = "00110110";
int k = 2;
if (hasAllcodes)
{
cout << "YES\n";
}
else
{
cout << "NO\n";
}
}
Java
// Java Program to Check If a
// String Contains All Binary
// Codes of Size K
import java.io.*;
import java.util.*;
class GFG
{
static boolean hasAllcodes(String s, int k)
{
// Unordered map of type string
Set<String> us= new HashSet<String>();
for(int i = 0; i + k <= s.length(); i++)
{
us.add(s.substring(i, i + k));
}
return (us.size() == (1 << k));
}
// Driver code
public static void main (String[] args)
{
String s = "00110110";
int k = 2;
if(hasAllcodes(s, k))
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 Program to Check If a
# String Contains All Binary
# Codes of Size K
def hasAllcodes(s, k) :
# Unordered map of type string
us = set()
for i in range(len(s) + 1) :
us.add(s[i : k])
return len(us) == 1 << k
# Driver code
s = "00110110"
k = 2
if (hasAllcodes) :
print("YES")
else :
print("NO")
# This code is contributed by divyeshrabadiya07
C#
// C# Program to Check If a
// String Contains All Binary
// Codes of Size K
using System;
using System.Collections.Generic;
class GFG {
static bool hasAllcodes(string s, int k)
{
// Unordered map of type string
HashSet<string> us = new HashSet<string>();
for (int i = 0; i + k <= s.Length; i++)
{
us.Add(s.Substring(i, k));
}
return us.Count == 1 << k;
}
// Driver code
static void Main()
{
string s = "00110110";
int k = 2;
if(hasAllcodes(s, k))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript program to Check If a
// String Contains All Binary
// Codes of Size K
function hasAllcodes(s,k)
{
// Unordered map of type string
let us = new Set();
for(let i = 0; i + k <= s.length; i++)
{
us.add(s.substring(i, i + k));
}
return (us.size == (1 << k));
}
// Driver code
let s = "00110110";
let k = 2;
if (hasAllcodes(s, k))
{
document.write("YES");
}
else
{
document.write("NO");
}
// This code is contributed by ab2127
</script>
YES
Método: 3 (basado en dos punteros)
En este método, tomaremos una ventana de tamaño k y moveremos esa ventana hasta el final, y marcaremos todas las permutaciones posibles en la array visitada. luego verifique si hay algún valor que no esté marcado como visitado y luego devuelva falso, de lo contrario, devuelva verdadero.
C++
#include <bits/stdc++.h>
using namespace std;
bool hasAllCodes(string s, int k)
{
int n = s.size();
if (n < k)
return false;
int size = pow(2, k);
vector<bool> visited(size, false);
int i = 0;
int j = 0;
int val = 0;
while (j < k - 1) {
val = 2 * val + (s[j] - '0');
j++;
}
while (j < n) {
val = 2 * val + (s[j] - '0');
visited[val] = true;
if (s[i] == '1')
val -= pow(2, k - 1);
j++;
i++;
}
for (int i = 0; i < size; i++) {
if (!visited[i])
return false;
}
return true;
}
// Driver Code
int main()
{
string s = "00110110";
int k = 2;
if (hasAllCodes(s, k)) {
cout << "YES\n";
}
else {
cout << "NO\n";
}
}
Java
// Java program to implement the approach
import java.util.*;
class GFG {
// Method to check if the string contnains
// all the binary codes of size k
static boolean hasAllCodes(String s, int k)
{
int n = s.length();
if (n < k)
return false;
int size = (int)Math.pow(2, k);
// ArrayList that tracks if a certain code
// has been found
ArrayList<Boolean> visited
= new ArrayList<Boolean>();
for (int i = 0; i < size; i++)
visited.add(false);
int i = 0;
int j = 0;
int val = 0;
while (j < k - 1) {
val = 2 * val + (s.charAt(j) - '0');
j++;
}
while (j < n) {
val = 2 * val + (s.charAt(j) - '0');
visited.set(val, true);
if (s.charAt(i) == '1')
val -= (int)Math.pow(2, k - 1);
j++;
i++;
}
// Checking if all the codes have been found
for (i = 0; i < size; i++) {
if (!visited.get(i))
return false;
}
return true;
}
// Driver Code
public static void main(String[] args)
{
String s = "00110110";
int k = 2;
// Function call
if (hasAllCodes(s, k)) {
System.out.print("YES\n");
}
else {
System.out.print("NO\n");
}
}
}
// This code is contributed by phasing17
Python3
# Python3 Program to Check If a String Contains All Binary Codes of Size K
def hasAllcodes(s, k):
n = s.len()
size = pow(2, k)
visited = [True for i in range(size)]
i = 0
j = 0
val = 0
while(j < k-1):
val = (2 * val) + (s[j] - '0')
j += 1
while(j < size):
val = (2 * val) + (s[j] - '0')
visited[val] = True
if(s[i] == '1'):
val = val - pow(2,k-1)
j += 1
i += 1
for i in range(size):
if(visited[i] == False):
return False
return True
# Driver code
s = "00110110"
k = 2
if (hasAllcodes):
print("YES")
else:
print("NO")
# This code is contributed by Ajay Makvana
Javascript
// JavaScript Program to Check If a String Contains All Binary Codes of Size K
function hasAllcodes(s, k)
{
var n = s.length;
var size = Math.pow(2, k);
var visited = new Array(size).fill(true);
var i = 0;
var j = 0;
var val = 0;
while (j < k-1)
{
val = (2 * val) + (s[j] - '0');
j += 1;
}
while (j < size)
{
val = (2 * val) + (s[j] - '0');
visited[val] = true;
if(s[i] == '1')
val = val - Math.pow(2, k - 1);
j += 1;
i += 1;
}
for (var i = 0; i < size; i++)
{
if(visited[i] == false)
return false;
}
return true;
}
// Driver code
var s = "00110110";
var k = 2;
if (hasAllcodes)
console.log("YES");
else
console.log("NO");
// This code is contributed by phasing17
YES
Time Complexity : O(n)
Publicación traducida automáticamente
Artículo escrito por Mithun Kumar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA