Mindestzeichen, die ersetzt werden müssen, um die angegebene Teilzeichenfolge zu entfernen
Gegeben seien zwei Strings str1 und str2 . Die Aufgabe besteht darin, die Mindestanzahl von Zeichen zu finden, die in Zeichenfolge str1 durch $ ersetzt werden müssen , sodass str1 keine Zeichenfolge str2 als Teilzeichenfolge enthält.
Beispiele:
Input: str1 = "intellect", str2 = "tell" Output: 1 4th character of string "str1" can be replaced by $ such that "int$llect" it does not contain "tell" as a substring. Input: str1 = "google", str2 = "apple" Output: 0
Die Vorgehensweise ähnelt der Suche nach Mustern | Set 1 (Naive Mustersuche) .
Die Idee ist, das am weitesten links stehende Vorkommen der Zeichenfolge „str2“ in der Zeichenfolge „str1“ zu finden. Wenn alle Zeichen von „str1“ mit „str2“ übereinstimmen, ersetzen wir das letzte Symbol des Vorkommens (oder erhöhen unsere Antwort um eins) und erhöhen den Index der Zeichenfolge „str1“, sodass erneut nach der Teilzeichenfolge nach gesucht wird ersetztes Zeichen (d. h. Index i ist gleich i+length(b)-1 ).
Unten ist die Implementierung des obigen Ansatzes:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// function to calculate minimum
// characters to replace
int replace(string A, string B)
{
int n = A.length(), m = B.length();
int count = 0, i, j;
for (i = 0; i < n; i++) {
for (j = 0; j < m; j++) {
// mismatch occurs
if (A[i + j] != B[j])
break;
}
// if all characters matched, i.e,
// there is a substring of 'a' which
// is same as string 'b'
if (j == m) {
count++;
// increment i to index m-1 such that
// minimum characters are replaced
// in 'a'
i += m - 1;
}
}
return count;
}
// Driver Code
int main()
{
string str1 = "aaaaaaaa";
string str2 = "aaa";
cout << replace(str1 , str2);
return 0;
}
Java
// Java implementation of
// above approach
import java.io.*;
// function to calculate minimum
// characters to replace
class GFG
{
static int replace(String A, String B)
{
int n = A.length(), m = B.length();
int count = 0, i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
// mismatch occurs
if(i + j >= n)
break;
else if (A.charAt(i + j) != B.charAt(j))
break;
}
// if all characters matched, i.e,
// there is a substring of 'a' which
// is same as string 'b'
if (j == m)
{
count++;
// increment i to index m-1 such that
// minimum characters are replaced
// in 'a'
i += m - 1;
}
}
return count;
}
// Driver Code
public static void main(String args[])
{
String str1 = "aaaaaaaa";
String str2 = "aaa";
System.out.println(replace(str1 , str2));
}
}
// This code is contributed by Subhadeep
Python3
# Python3 implementation of the # above approach # Function to calculate minimum # characters to replace def replace(A, B): n, m = len(A), len(B) count, i = 0, 0 while i < n: j = 0 while j < m: # mismatch occurs if i + j >= n or A[i + j] != B[j]: break j += 1 # If all characters matched, i.e, # there is a substring of 'a' which # is same as string 'b' if j == m: count += 1 # increment i to index m-1 such that # minimum characters are replaced # in 'a' i += m - 1 i += 1 return count # Driver Code if __name__ == "__main__": str1 = "aaaaaaaa" str2 = "aaa" print(replace(str1 , str2)) # This code is contributed by Rituraj Jain
C#
// C# implementation of above approach
using System;
// function to calculate minimum
// characters to replace
class GFG
{
public static int replace(string A,
string B)
{
int n = A.Length, m = B.Length;
int count = 0, i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < m; j++)
{
// mismatch occurs
if (i + j >= n)
{
break;
}
else if (A[i + j] != B[j])
{
break;
}
}
// if all characters matched, i.e,
// there is a substring of 'a'
// which is same as string 'b'
if (j == m)
{
count++;
// increment i to index m-1
// such that minimum characters
// are replaced in 'a'
i += m - 1;
}
}
return count;
}
// Driver Code
public static void Main(string[] args)
{
string str1 = "aaaaaaaa";
string str2 = "aaa";
Console.WriteLine(replace(str1, str2));
}
}
// This code is contributed
// by Shrikant13
PHP
<?php
// PHP implementation of above approach
// function to calculate minimum
// characters to replace
function replace($A, $B)
{
$n = strlen($A);
$m = strlen($B);
$count = 0;
for ($i = 0; $i < $n; $i++)
{
for ($j = 0; $j < $m; $j++)
{
// mismatch occurs
if ($i + $j >= $n)
{
break;
}
else if ($A[$i + $j] != $B[$j])
{
break;
}
}
// if all characters matched, i.e,
// there is a substring of 'a'
// which is same as string 'b'
if ($j == $m)
{
$count++;
// increment i to index m-1
// such that minimum characters
// are replaced in 'a'
$i = $i + $m - 1;
}
}
return $count;
}
// Driver Code
$str1 = "aaaaaaaa";
$str2 = "aaa";
echo (replace($str1, $str2));
// This code is contributed
// by Kirti_Mangal
?>
2
Zeitkomplexität: O(len1 * len2) , wobei len1 die Länge der ersten Zeichenfolge und len2 die Länge der zweiten Zeichenfolge ist.
Dieses Problem kann auch direkt gelöst werden, indem die in Python eingebaute Funktion string1.count(string2) verwendet wird.
// Python program to find minimum numbers // of characters to be replaced to // remove the given substring str1 = "aaaaaaaa" str2 = "aaa" # inbuilt function answer = str1.count(str2) print(answer)
2
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .