给两个字符串 str1 和 str2 。任务是找到要替换的最小字符数 $ 串起 str1 以至于 str1 不包含字符串 str2 就像任何子串一样。 例如：
null
Input: str1 = "intellect", str2 = "tell"Output: 14th 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
方法 类似于 搜索模式|集1（简单模式搜索） . 其思想是在字符串“str1”中找到字符串“str2”最左边的匹配项。如果“str1”的所有字符都与“str2”匹配，我们将替换（或用一个递增答案）出现的最后一个符号，并递增字符串“str1”的索引，以便它再次检查替换字符后的子字符串（即索引i将等于 i+长度（b）-1 ). 以下是上述方法的实施情况：
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 ?> |
Javascript
<script> // JavaScript implementation of above approach // function to calculate minimum // characters to replace function replace(A,B) { let n = A.length, m = B.length; let 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 const str1 = "aaaaaaaa" ; const str2 = "aaa" ; document.write(replace(str1 , str2)); // This code is contributed by shinjanpatra. </script> |
输出：
2
时间复杂性： O（len1*len2） ，其中len1是第一个字符串的长度，len2是第二个字符串的长度。 此外，这个问题可以通过使用Python的内置函数直接解决- string1。计数（string2）
Python3
/ / 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
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
