Dada una string str y una array de strings arr[] , la tarea es encontrar el recuento mínimo de substrings en las que se puede dividir de tal manera que cada substring esté presente en la array de strings dada arr[] .
Ejemplos:
Entrada: str = “111112”, arr[] = {“11”, “111”, “11111”, “2”}
Salida: 2
“11111” y “2” son las substrings requeridas.
“11”, “111” y “2” también pueden ser una respuesta válida
pero no es la mínima.Entrada: str = “123456”, arr[] = {“1”, “12345”, “2345”, “56”, “23”, “456”}
Salida: 3
Enfoque: itere la string desde el índice 0 y construya la string de prefijo, si la string de prefijo existe en la array dada (se puede usar un conjunto para verificar esto), luego llame a la función nuevamente desde la siguiente posición en la string y realice un seguimiento de la recuento mínimo general de substrings.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Set to store all the strings
// from the given array
unordered_set<string> uSet;
// To store the required count
int minCnt = INT_MAX;
// Recursive function to find the count of
// substrings that can be splitted starting
// from the index start such that all
// the substrings are present in the map
void findSubStr(string str, int cnt, int start)
{
// All the chosen substrings
// are present in the map
if (start == str.length()) {
// Update the minimum count
// of substrings
minCnt = min(cnt, minCnt);
}
// Starting from the substrings of length 1
// that start with the given index
for (int len = 1; len <= (str.length() - start); len++) {
// Get the substring
string subStr = str.substr(start, len);
// If the substring is present in the set
if (uSet.find(subStr) != uSet.end()) {
// Recursive call for the
// rest of the string
findSubStr(str, cnt + 1, start + len);
}
}
}
// Function that inserts all the strings
// from the given array in a set and calls
// the recursive function to find the
// minimum count of substrings str can be
// splitted into that satisfy the given condition
void findMinSubStr(string arr[], int n, string str)
{
// Insert all the strings from
// the given array in a set
for (int i = 0; i < n; i++)
uSet.insert(arr[i]);
// Find the required count
findSubStr(str, 0, 0);
}
// Driver code
int main()
{
string str = "123456";
string arr[] = { "1", "12345", "2345",
"56", "23", "456" };
int n = sizeof(arr) / sizeof(string);
findMinSubStr(arr, n, str);
cout << minCnt;
return 0;
}
Java
//Java implementation of above approach
import java.util.*;
class GFG
{
// Set to store all the Strings
// from the given array
static Set<String> uSet = new HashSet<String>();
// To store the required count
static int minCnt = Integer.MAX_VALUE;
// Recursive function to find the count of
// subStrings that can be splitted starting
// from the index start such that all
// the subStrings are present in the map
static void findSubStr(String str, int cnt, int start)
{
// All the chosen subStrings
// are present in the map
if (start == str.length())
{
// Update the minimum count
// of subStrings
minCnt = Math.min(cnt, minCnt);
}
// Starting from the subStrings of length 1
// that start with the given index
for (int len = 1;
len <= (str.length() - start); len++)
{
// Get the subString
String subStr = str.substring(start, start + len);
// If the subString is present in the set
if (uSet.contains(subStr))
{
// Recursive call for the
// rest of the String
findSubStr(str, cnt + 1, start + len);
}
}
}
// Function that inserts all the Strings
// from the given array in a set and calls
// the recursive function to find the
// minimum count of subStrings str can be
// splitted into that satisfy the given condition
static void findMinSubStr(String arr[],
int n, String str)
{
// Insert all the Strings from
// the given array in a set
for (int i = 0; i < n; i++)
uSet.add(arr[i]);
// Find the required count
findSubStr(str, 0, 0);
}
// Driver code
public static void main(String args[])
{
String str = "123456";
String arr[] = {"1", "12345", "2345",
"56", "23", "456" };
int n = arr.length;
findMinSubStr(arr, n, str);
System.out.print(minCnt);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach import sys # Set to store all the strings # from the given array uSet = set(); # To store the required count minCnt = sys.maxsize; # Recursive function to find the count of # substrings that can be splitted starting # from the index start such that all # the substrings are present in the map def findSubStr(string, cnt, start) : global minCnt; # All the chosen substrings # are present in the map if (start == len(string)) : # Update the minimum count # of substrings minCnt = min(cnt, minCnt); # Starting from the substrings of length 1 # that start with the given index for length in range(1, len(string) - start + 1) : # Get the substring subStr = string[start : start + length]; # If the substring is present in the set if subStr in uSet : # Recursive call for the # rest of the string findSubStr(string, cnt + 1, start + length); # Function that inserts all the strings # from the given array in a set and calls # the recursive function to find the # minimum count of substrings str can be # splitted into that satisfy the given condition def findMinSubStr(arr, n, string) : # Insert all the strings from # the given array in a set for i in range(n) : uSet.add(arr[i]); # Find the required count findSubStr(string, 0, 0); # Driver code if __name__ == "__main__" : string = "123456"; arr = ["1", "12345", "2345", "56", "23", "456" ]; n = len(arr); findMinSubStr(arr, n, string); print(minCnt); # This code is contributed by AnkitRai01
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// Set to store all the Strings
// from the given array
static HashSet<String> uSet = new HashSet<String>();
// To store the required count
static int minCnt = int.MaxValue;
// Recursive function to find the count of
// subStrings that can be splitted starting
// from the index start such that all
// the subStrings are present in the map
static void findSubStr(String str, int cnt, int start)
{
// All the chosen subStrings
// are present in the map
if (start == str.Length)
{
// Update the minimum count
// of subStrings
minCnt = Math.Min(cnt, minCnt);
}
// Starting from the subStrings of length 1
// that start with the given index
for (int len = 1;
len <= (str.Length - start); len++)
{
// Get the subString
String subStr = str.Substring(start, len);
// If the subString is present in the set
if (uSet.Contains(subStr))
{
// Recursive call for the
// rest of the String
findSubStr(str, cnt + 1, start + len);
}
}
}
// Function that inserts all the Strings
// from the given array in a set and calls
// the recursive function to find the
// minimum count of subStrings str can be
// splitted into that satisfy the given condition
static void findMinSubStr(String []arr,
int n, String str)
{
// Insert all the Strings from
// the given array in a set
for (int i = 0; i < n; i++)
uSet.Add(arr[i]);
// Find the required count
findSubStr(str, 0, 0);
}
// Driver code
public static void Main(String []args)
{
String str = "123456";
String []arr = {"1", "12345", "2345",
"56", "23", "456" };
int n = arr.Length;
findMinSubStr(arr, n, str);
Console.WriteLine(minCnt);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Set to store all the strings
// from the given array
var uSet = new Set();
// To store the required count
var minCnt = 1000000000;
// Recursive function to find the count of
// substrings that can be splitted starting
// from the index start such that all
// the substrings are present in the map
function findSubStr( str, cnt, start)
{
// All the chosen substrings
// are present in the map
if (start == str.length) {
// Update the minimum count
// of substrings
minCnt = Math.min(cnt, minCnt);
}
// Starting from the substrings of length 1
// that start with the given index
for (var len = 1; len <= (str.length - start); len++) {
// Get the substring
var subStr = str.substring(start, start+len);
// If the substring is present in the set
if (uSet.has(subStr)) {
// Recursive call for the
// rest of the string
findSubStr(str, cnt + 1, start + len);
}
}
}
// Function that inserts all the strings
// from the given array in a set and calls
// the recursive function to find the
// minimum count of substrings str can be
// splitted into that satisfy the given condition
function findMinSubStr(arr, n, str)
{
// Insert all the strings from
// the given array in a set
for (var i = 0; i < n; i++)
uSet.add(arr[i]);
// Find the required count
findSubStr(str, 0, 0);
}
// Driver code
var str = "123456";
var arr = ["1", "12345", "2345",
"56", "23", "456"];
var n = arr.length;
findMinSubStr(arr, n, str);
document.write( minCnt);
</script>
Producción:
3
Publicación traducida automáticamente
Artículo escrito por AyanChowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA