srcmini本文概述
给定两个字符串A和B, 任务是尽可能将A转换为B。唯一允许的操作是将A中的任何字符放入前面。查找是否可以转换字符串。如果是, 则输出最小值。转换所需的操作。
例子：
Input: A = "ABD", B = "BAD"
Output: 1
Explanation: Pick B and insert it at front.
Input: A = "EACBD", B = "EABCD"
Output: 3
Explanation: Pick B and insert at front, EACBD => BEACD
Pick A and insert at front, BEACD => ABECD
Pick E and insert at front, ABECD => EABCD检查字符串是否可以转换为另一个很简单。我们需要检查两个字符串是否具有相同数量的字符和相同的字符集。通过为第一个字符串创建计数数组并检查第二个字符串的每个字符计数是否相同, 可以轻松完成此操作。
当我们确定可以将A转换为B时, 如何找到最小的操作数？这个想法是从两个字符串的最后一个字符开始匹配。如果最后一个字符匹配, 那么我们的任务将减少为n-1个字符。如果最后一个字符不匹配, 则找到B不匹配字符在A中的位置。两个位置之间的差异表明, 必须将A的许多字符移动到A的当前字符之前。
下面是完整的算法。
1)通过首先为A的所有字符创建一个计数数组, 然后与B一起检查B是否对每个字符都有相同的计数, 来查找A是否可以转换为B。
2)将结果初始化为0。
2)从两个字符串的末尾开始遍历。
……a)如果A和B的当前字符匹配, 即A [i] == B [j]
………那么我= i-1和j = j-1
……b)如果当前字符不匹配, 则在剩余字符中搜索B [j]
………一种。搜索时, 请保持递增结果, 因为这些字符
…………必须向前推进以实现A到B的转型。
以下是基于此想法的实现。
C ++
// C++ program to find minimum number of
// operations required to transform one string to other
#include<bits/stdc++.h>
using namespace std;
// Function to find minimum number of operations required to transform
// A to B.
int minOps(string& A, string& B)
{
int m = A.length(), n = B.length();
// This parts checks whether conversion is
// possible or not
if (n != m)
return -1;
int count[256];
memset (count, 0, sizeof (count));
for ( int i=0; i<n; i++) // count characters in A
count[B[i]]++;
for ( int i=0; i<n; i++) // subtract count for
count[A[i]]--; // every character in B
for ( int i=0; i<256; i++) // Check if all counts become 0
if (count[i])
return -1;
// This part calculates the number of operations required
int res = 0;
for ( int i=n-1, j=n-1; i>=0; )
{
// If there is a mismatch, then keep incrementing
// result 'res' until B[j] is not found in A[0..i]
while (i>=0 && A[i] != B[j])
{
i--;
res++;
}
// If A[i] and B[j] match
if (i >= 0)
{
i--;
j--;
}
}
return res;
}
// Driver program
int main()
{
string A = "EACBD" ;
string B = "EABCD" ;
cout << "Minimum number of operations "
"required is " << minOps(A, B);
return 0;
}Java
// Java program to find minimum number of
// operations required to transform one
// string to other
import java.io.*;
import java.util.*;
public class GFG {
// Function to find minimum number of
// operations required to transform
// A to B.
public static int minOps(String A, String B)
{
// This parts checks whether conversion is
// possible or not
if (A.length() != B.length())
return - 1 ;
int i, j, res = 0 ;
int count [] = new int [ 256 ];
// count characters in A
// subtract count for every character in B
for (i = 0 ; i < A.length(); i++)
{
count[A.charAt(i)]++;
count[B.charAt(i)]--;
}
// Check if all counts become 0
for (i = 0 ; i < 256 ; i++)
if (count[i] != 0 )
return - 1 ;
i = A.length() - 1 ;
j = B.length() - 1 ;
while (i >= 0 )
{
// If there is a mismatch, then
// keep incrementing result 'res'
// until B[j] is not found in A[0..i]
if (A.charAt(i) != B.charAt(j))
res++;
else
j--;
i--;
}
return res;
}
// Driver code
public static void main(String[] args)
{
String A = "EACBD" ;
String B = "EABCD" ;
System.out.println( "Minimum number of "
+ "operations required is "
+ minOps(A, B));
}
}
// This code is contributed by Dipesh Jain
// (dipesh_jain)python
# Python program to find the minimum number of
# operations required to transform one string to other
# Function to find minimum number of operations required
# to transform A to B
def minOps(A, B):
m = len (A)
n = len (B)
# This part checks whether conversion is possible or not
if n ! = m:
return - 1
count = [ 0 ] * 256
for i in xrange (n): # count characters in A
count[ ord (B[i])] + = 1
for i in xrange (n): # subtract count for every char in B
count[ ord (A[i])] - = 1
for i in xrange ( 256 ): # Check if all counts become 0
if count[i]:
return - 1
# This part calculates the number of operations required
res = 0
i = n - 1
j = n - 1
while i > = 0 :
# if there is a mismatch, then keep incrementing
# result 'res' until B[j] is not found in A[0..i]
while i> = 0 and A[i] ! = B[j]:
i - = 1
res + = 1
# if A[i] and B[j] match
if i > = 0 :
i - = 1
j - = 1
return res
# Driver program
A = "EACBD"
B = "EABCD"
print "Minimum number of operations required is " + str (minOps(A, B))
# This code is contributed by Bhavya JainC#
// C# program to find minimum number of
// operations required to transform one
// string to other
using System;
class GFG
{
// Function to find minimum number of
// operations required to transform
// A to B.
public static int minOps( string A, string B)
{
// This parts checks whether
// conversion is possible or not
if (A.Length != B.Length)
{
return -1;
}
int i, j, res = 0;
int [] count = new int [256];
// count characters in A
// subtract count for every
// character in B
for (i = 0; i < A.Length; i++)
{
count[A[i]]++;
count[B[i]]--;
}
// Check if all counts become 0
for (i = 0; i < 256; i++)
{
if (count[i] != 0)
{
return -1;
}
}
i = A.Length - 1;
j = B.Length - 1;
while (i >= 0)
{
// If there is a mismatch, then
// keep incrementing result 'res'
// until B[j] is not found in A[0..i]
if (A[i] != B[j])
{
res++;
}
else
{
j--;
}
i--;
}
return res;
}
// Driver code
public static void Main( string [] args)
{
string A = "EACBD" ;
string B = "EABCD" ;
Console.WriteLine( "Minimum number of " +
"operations required is " +
minOps(A, B));
}
}
// This code is contributed by Shrikant13的PHP
<?php
// PHP program to find minimum number of
// operations required to transform one string to other
// Function to find minimum number of operations required to transform
// A to B.
function minOps( $A , $B )
{
$m = strlen ( $A );
$n = strlen ( $B );
// This parts checks whether conversion is
// possible or not
if ( $n != $m )
return -1;
$count = array_fill (0, 256, NULL);
for ( $i =0; $i < $n ; $i ++) // count characters in A
$count [ord( $B [ $i ])]++;
for ( $i =0; $i < $n ; $i ++) // subtract count for
$count [ord( $A [ $i ])]--; // every character in B
for ( $i =0; $i <256; $i ++) // Check if all counts become 0
if ( $count [ $i ])
return -1;
// This part calculates the number of operations required
$res = 0;
for ( $i = $n -1, $j = $n -1; $i >=0; )
{
// If there is a mismatch, then keep incrementing
// result 'res' until B[j] is not found in A[0..i]
while ( $i >=0 && $A [ $i ] != $B [ $j ])
{
$i --;
$res ++;
}
// If A[i] and B[j] match
if ( $i >= 0)
{
$i --;
$j --;
}
}
return $res ;
}
// Driver program
$A = "EACBD" ;
$B = "EABCD" ;
echo "Minimum number of operations " .
"required is " . minOps( $A , $B );
return 0;
?>输出如下：
Minimum number of operations required is 3时间复杂度：O(n), 请注意, i总是递减的(在while循环和if中), 并且for循环从n-1开始并在i> = 0时运行。
感谢Gaurav Ahirwar提供上述解决方案。
如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
评论前必须登录！
注册