Dadas dos strings str1 y str2, la tarea es encontrar el número mínimo de prefijos y sufijos de str2 necesarios para formar la string str1. Si la tarea no es posible, devuelva «-1».
Ejemplo:
Entrada : str1 = «HELLOWORLD», str2 = «OWORLDHELL»
Salida : 2
Explicación : la string anterior se puede formar como «HELL» + «OWORLD», que son el sufijo y el prefijo de la string str2Entrada : str = «GEEKSFORGEEKS», wrd = «SFORGEEK»
Salida : 3
Explicación : «GEEK» + «SFORGEEK» + «S»
Enfoque : El problema anterior se puede resolver usando programación dinámica . Siga los pasos a continuación para resolver el problema:
- Inicialice una array dp donde el i-ésimo elemento arr[i] almacenará la concatenación mínima requerida para formar una string hasta el índice de prefijo i
- Inicializar dp[0] = 0 y otros valores de la array dp a -1
- Inicializar un conjunto HashSet
- Iterar la string str1 de izquierda a derecha y en cada índice i :
- Agregue la substring del índice 0 al índice actual i en el conjunto HashSet
- Iterar la string str1 de derecha a izquierda y en cada índice i :
- Agregue la substring del índice i al índice final en el conjunto HashSet
- Verifique todas las substrings en la string str1 y actualice el dp, en consecuencia
- La respuesta final se almacenará en dp[N], donde N es la longitud de la string str1
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum number of
// concatenation of prefix and suffix
// of str2 to make str1
int partCount(string str1, string str2)
{
// Initialize a set
unordered_set<string> set;
// Initialize a temporary string
string temp = "";
int l1 = str1.length(), l2 = str2.length();
// Iterate the string str2
// from left to right
for (int i = 0; i < l2; i++) {
// Add current character
// to string temp
temp += str2[i];
// Insert the prefix into hashset
set.insert(temp);
}
// Re-initialize temp string
// to empty string
temp = "";
// Iterate the string in reverse direction
for (int i = l2 - 1; i >= 0; i--) {
// Add current character to temp
temp += str2[i];
// Reverse the string temp
reverse(temp.begin(), temp.end());
// Insert the suffix into the hashset
set.insert(temp);
// Reverse the string temp again
reverse(temp.begin(), temp.end());
}
// Initialize dp array to store the answer
int dp[str1.length() + 1];
memset(dp, -1, sizeof(dp));
dp[0] = 0;
// Check for all substrings starting
// and ending at every indices
for (int i = 0; i < l1; i++) {
for (int j = 1; j <= l1 - i; j++) {
// HashSet contains the substring
if (set.count(str1.substr(i, j))) {
if (dp[i] == -1) {
continue;
}
if (dp[i + j] == -1) {
dp[i + j] = dp[i] + 1;
}
else {
// Minimum of dp[i + j] and
// dp[i] + 1 will be stored
dp[i + j]
= min(dp[i + j], dp[i] + 1);
}
}
}
}
// Return the answer
return dp[str1.size()];
}
// Driver Code
int main()
{
string str = "GEEKSFORGEEKS",
wrd = "SFORGEEK";
// Print the string
cout << partCount(str, wrd);
}
Java
// Java implementation for the above approach
import java.util.Arrays;
import java.util.HashSet;
class GFG {
// Function to find minimum number of
// concatenation of prefix and suffix
// of str2 to make str1
public static int partCount(String str1, String str2) {
// Initialize a set
HashSet<String> set = new HashSet<String>();
// Initialize a temporary string
String temp = "";
int l1 = str1.length(), l2 = str2.length();
// Iterate the string str2
// from left to right
for (int i = 0; i < l2; i++) {
// Add current character
// to string temp
temp += str2.charAt(i);
// Insert the prefix into hashset
set.add(temp);
}
// Re-initialize temp string
// to empty string
temp = "";
// Iterate the string in reverse direction
for (int i = l2 - 1; i >= 0; i--) {
// Add current character to temp
temp += str2.charAt(i);
// Reverse the string temp
temp = new StringBuffer(temp).reverse().toString();
// Insert the suffix into the hashet
set.add(temp);
// Reverse the string temp again
temp = new StringBuffer(temp).reverse().toString();
}
// Initialize dp array to store the answer
int[] dp = new int[str1.length() + 1];
Arrays.fill(dp, -1);
dp[0] = 0;
// Check for all substrings starting
// and ending at every indices
for (int i = 0; i < l1; i++) {
for (int j = 1; j <= l1 - i; j++) {
// HashSet contains the substring
if (set.contains(str1.substring(i, i + j))) {
if (dp[i] == -1) {
continue;
}
if (dp[i + j] == -1) {
dp[i + j] = dp[i] + 1;
} else {
// Minimum of dp[i + j] and
// dp[i] + 1 will be stored
dp[i + j] = Math.min(dp[i + j], dp[i] + 1);
}
}
}
}
// Return the answer
return dp[str1.length()];
}
// Driver Code
public static void main(String args[]) {
String str = "GEEKSFORGEEKS", wrd = "SFORGEEK";
// Print the string
System.out.println(partCount(str, wrd));
}
}
// This code is contributed by gfgking.
Python3
# Python3 implementation for the above approach
# Function to find minimum number of
# concatenation of prefix and suffix
# of str2 to make str1
def partCount(str1, str2):
# Initialize a set
se = set()
# Initialize a temporary string
temp = ""
l1 = len(str1)
l2 = len(str2)
# Iterate the string str2
# from left to right
for i in range(0, l2):
# Add current character
# to string temp
temp += str2[i]
# Insert the prefix into hashset
se.add(temp)
# Re-initialize temp string
# to empty string
temp = []
# Iterate the string in reverse direction
for i in range(l2 - 1, -1, -1):
# Add current character to temp
temp.append(str2[i])
# Reverse the string temp
temp.reverse()
# Insert the suffix into the hashet
se.add(''.join(temp))
# Reverse the string temp again
temp.reverse()
# Initialize dp array to store the answer
dp = [-1 for _ in range(len(str1) + 1)]
dp[0] = 0
# Check for all substrings starting
# and ending at every indices
for i in range(0, l1, 1):
for j in range(1, l1 - i + 1):
# HashSet contains the substring
if (str1[i:i+j] in se):
if (dp[i] == -1):
continue
if (dp[i + j] == -1):
dp[i + j] = dp[i] + 1
else:
# Minimum of dp[i + j] and
# dp[i] + 1 will be stored
dp[i + j] = min(dp[i + j], dp[i] + 1)
# Return the answer
return dp[len(str1)]
# Driver Code
if __name__ == "__main__":
str = "GEEKSFORGEEKS"
wrd = "SFORGEEK"
# Print the string
print(partCount(str, wrd))
# This code is contributed by rakeshsahni
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
class GFG
{
public static string Reverse(string Input)
{
// Converting string to character array
char[] charArray = Input.ToCharArray();
// Declaring an empty string
string reversedString = String.Empty;
// Iterating the each character from right to left
for(int i = charArray.Length - 1; i > -1; i--)
{
// Append each character to the reversedstring.
reversedString += charArray[i];
}
// Return the reversed string.
return reversedString;
}
// Function to find minimum number of
// concatenation of prefix and suffix
// of str2 to make str1
public static int partCount(string str1, string str2) {
// Initialize a set
HashSet<String> set = new HashSet<String>();
// Initialize a temporary string
string temp = "";
int l1 = str1.Length, l2 = str2.Length;
// Iterate the string str2
// from left to right
for (int i = 0; i < l2; i++) {
// Add current character
// to string temp
temp += str2[i];
// Insert the prefix into hashset
set.Add(temp);
}
// Re-initialize temp string
// to empty string
temp = "";
// Iterate the string in reverse direction
for (int i = l2 - 1; i >= 0; i--) {
// Add current character to temp
temp += str2[i];
// Reverse the string temp
temp = Reverse(temp);
// Insert the suffix into the hashet
set.Add(temp);
// Reverse the string temp again
temp = Reverse(temp);
}
// Initialize dp array to store the answer
int[] dp = new int[str1.Length + 1];
for(int j=0; j<dp.Length;j++)
{
dp[j] = -1;
}
dp[0] = 0;
// Check for all substrings starting
// and ending at every indices
for (int i = 0; i < l1; i++) {
for (int j = 1; j <= l1 - i; j++) {
// HashSet contains the substring
if (set.Contains(str1.Substring(i, j))) {
if (dp[i] == -1) {
continue;
}
if (dp[i + j] == -1) {
dp[i + j] = dp[i] + 1;
} else {
// Minimum of dp[i + j] and
// dp[i] + 1 will be stored
dp[i + j] = Math.Min(dp[i + j], dp[i] + 1);
}
}
}
}
// Return the answer
return dp[str1.Length];
}
// Driver code
static public void Main(String[] args)
{
string str = "GEEKSFORGEEKS", wrd = "SFORGEEK";
// Print the string
Console.WriteLine(partCount(str, wrd));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find minimum number of
// concatenation of prefix and suffix
// of str2 to make str1
function partCount(str1, str2) {
// Initialize a set
let set = new Set();
// Initialize a temporary string
let temp = "";
let l1 = str1.length, l2 = str2.length;
// Iterate the string str2
// from left to right
for (let i = 0; i < l2; i++) {
// Add current character
// to string temp
temp = temp + str2.charAt(i);
// Insert the prefix into hashset
set.add(temp);
}
// Re-initialize temp string
// to empty string
temp = "";
// Iterate the string in reverse direction
for (let i = l2 - 1; i >= 0; i--) {
// Add current character to temp
temp = temp + str2.charAt(i);
// Reverse the string temp
temp = temp.split('').reduce((r, c) => c + r, '');
// Insert the suffix into the hashet
set.add(temp);
// Reverse the string temp again
temp = temp.split('').reduce((r, c) => c + r, '');
}
// Initialize dp array to store the answer
let dp = new Array(str1.length + 1).fill(-1);
dp[0] = 0;
// Check for all substrings starting
// and ending at every indices
for (let i = 0; i < l1; i++) {
for (let j = 1; j <= l1 - i; j++) {
// HashSet contains the substring
if (set.has(str1.substring(i, j))) {
if (dp[i] == -1) {
continue;
}
if (dp[i + j] == -1) {
dp[i + j] = dp[i] + 1;
}
else {
// Minimum of dp[i + j] and
// dp[i] + 1 will be stored
dp[i + j]
= Math.min(dp[i + j], dp[i] + 1);
}
}
}
}
// Return the answer
return dp[str1.length] + 1;
}
// Driver Code
let str = "GEEKSFORGEEKS"
let wrd = "SFORGEEK";
// Print the string
document.write(partCount(str, wrd));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad de tiempo: O(N^2), donde N es la longitud de str1
Espacio auxiliar: O(N^2)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA