当前位置： 正文

使用最少的给定操作数将一个字符串转换为另一个字符串

03-19 面试题/算法&算力分析 346

本文概述

给定两个字符串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 Jain

C#

// 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提供上述解决方案。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

微信公众号
手机浏览(小程序)
0
分享到：

猜你喜欢

用php找出字符串中连续重复次数最多的字符，你有方法吗？
面试题/算法&算力分析

05-06 2033
php编写函数取得上一月的最后一天
面试题/算法&算力分析

04-11 1121
php自定义错误处理器
面试题/算法&算力分析

04-11 693
PHP错误级别错误类型
面试题/算法&算力分析

04-11 719
php去掉字段文本的所有html标签
面试题/算法&算力分析

04-11 683
php写出一个正则表达式，过虑网页上的所有JS/VBS脚本（即把script标记及其内容都去掉）
面试题/算法&算力分析

04-11 676
没有账号？ 忘记密码？