在不删除字符的情况下生成两个字符串的字谜所需的最小操作次数-yiteyi-C++库

给两条线 s1 和 s2 ，我们需要找到在不删除任何字符的情况下生成两个字符串的字谜所需的最小操作次数。

null

注：- 字谜字符串具有相同的字符集，字符序列可以不同。如果允许删除字符并给出了费用，请参阅使两个字符串相同的最低成本问题来源：雅特拉。com面试体验|第7组

例如：

Input :        s1 = "aba"       s2 = "baa"Output : 0Explanation: Both String contains identical charactersInput :       s1 = "ddcf"       s2 = "cedk"Output : 2Explanation : Here, we need to change two charactersin either of the strings to make them identical. We can change 'd' and 'f' in s1 or 'e' and 'k' in s2.

假设： 两条弦的长度被认为是相似的

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

C++

                         // C++ Program to find minimum number                       
                         // of manipulations required to make                       
                         // two strings identical                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                                                 // Counts the no of manipulations                       
                                                 // required                       
                                                 int                                     countManipulations(string s1, string s2)                       
                                                 {                       
                                   
                                                 int                                     count = 0;                       
           
                                                 // store the count of character                       
                                                 int                                     char_count[26];                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < 26; i++)                       
                                                 {                       
                                                 char_count[i] = 0;                       
                                                 }                       
           
                                                 // iterate though the first String                       
                                                 // and update count                       
                                                 for                                     (                                     int                                     i = 0; i < s1.length(); i++)                       
                                                 char_count[s1[i] -                                     'a'                                     ]++;                       
           
                                                 // iterate through the second string                       
                                                 // update char_count.                       
                                                 // if character is not found in                       
                                                 // char_count then increase count                       
                                                 for                                     (                                     int                                     i = 0; i < s2.length(); i++)                       
                                                 {                       
                                                 char_count[s2[i] -                                     'a'                                     ]--;                       
                                                 }                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < 26; ++i)                       
                                                 {                       
                                                 if                                     (char_count[i] != 0)                       
                                                 {                       
                                                 count+=                                     abs                                     (char_count[i]);                       
                                                 }                       
                                                 }                       
                                                 return                                     count / 2;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 int                                     main()                       
                                                 {                       
           
                                                 string s1 =                                     "ddcf"                                     ;                       
                                                 string s2 =                                     "cedk"                                     ;                       
                                   
                                                 cout<<countManipulations(s1, s2);                       
                                                 }                       
                                   
                         // This code is contributed by vt_m.                       

JAVA

                         // Java Program to find minimum number of manipulations                       
                         // required to make two strings identical                       
                         public                                     class                                     Similar_strings {                       
           
                                                 // Counts the no of manipulations required                       
                                                 static                                     int                                     countManipulations(String s1, String s2)                       
                                                 {                       
                                                 int                                     count =                                     0                                     ;                       
           
                                                 // store the count of character                       
                                                 int                                     char_count[] =                                     new                                     int                                     [                                     26                                     ];                       
           
                                                 // iterate though the first String and update                       
                                                 // count                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < s1.length(); i++)                       
                                                 char_count[s1.charAt(i) -                                     'a'                                     ]++;                       
           
                                                 // iterate through the second string                       
                                                 // update char_count.                       
                                                 // if character is not found in char_count                       
                                                 // then increase count                       
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < s2.length(); i++)                       
                                                 {                       
                                                 char_count[s2.charAt(i) -                                     'a'                                     ]--;                       
                                                 }                       
                                   
                                                 for                                     (                                     int                                     i =                                     0                                     ; i <                                     26                                     ; ++i)                       
                                                 {                       
                                                 if                                     (char_count[i] !=                                     0                                     )                       
                                                 {                       
                                                 count+= Math.abs(char_count[i]);                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     count /                                     2                                     ;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
           
                                                 String s1 =                                     "ddcf"                                     ;                       
                                                 String s2 =                                     "cedk"                                     ;                       
                                                 System.out.println(countManipulations(s1, s2));                       
                                                 }                       
                         }                       

Python3

                         # Python3 Program to find minimum number                       
                         # of manipulations required to make                       
                         # two strings identical                       
           
                         # Counts the no of manipulations                       
                         # required                       
                         def                                     countManipulations(s1, s2):                       
                                   
                                                 count                                     =                                     0                       
           
                                                 # store the count of character                       
                                                 char_count                                     =                                     [                                     0                                     ]                                     *                                     26                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     26                                     ):                       
                                                 char_count[i]                                     =                                     0                       
           
                                                 # iterate though the first String                       
                                                 # and update count                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     ( s1)):                       
                                                 char_count[                                     ord                                     (s1[i])                                     -                       
                                                 ord                                     (                                     'a'                                     )]                                     +                                     =                                     1                       
           
                                                 # iterate through the second string                       
                                                 # update char_count.                       
                                                 # if character is not found in                       
                                                 # char_count then increase count                       
                                                 for                                     i                                     in                                     range                                     (                                     len                                     (s2)):                       
                                                 char_count[                                     ord                                     (s2[i])                                     -                                     ord                                     (                                     'a'                                     )]                                     -                                     =                                     1                       
                                   
                                                 for                                     i                                     in                                     range                                     (                                     26                                     ):                       
                                                 if                                     char_count[i] !                                     =                                     0                                     :                       
                                                 count                                     +                                     =                                     abs                                     (char_count[i])                       
                                   
           
                                                 return                                     count                                     /                                     2                       
           
                         # Driver code                       
                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       
           
                                                 s1                                     =                                     "ddcf"                       
                                                 s2                                     =                                     "cedk"                       
                                   
                                                 print                                     (countManipulations(s1, s2))                       
           
                         # This code is contributed by ita_c                       

C#

                         // C# Program to find minimum number                       
                         // of manipulations required to make                       
                         // two strings identical                       
                         using                                     System;                       
           
                         public                                     class                                     GFG {                       
           
                                                 // Counts the no of manipulations                       
                                                 // required                       
                                                 static                                     int                                     countManipulations(                                     string                                     s1,                       
                                                 string                                     s2)                       
                                                 {                       
                                                 int                                     count = 0;                       
           
                                                 // store the count of character                       
                                                 int                                     []char_count =                                     new                                     int                                     [26];                       
           
                                                 // iterate though the first String                       
                                                 // and update count                       
                                                 for                                     (                                     int                                     i = 0; i < s1.Length; i++)                       
                                                 char_count[s1[i] -                                     'a'                                     ]++;                       
           
                                                 // iterate through the second string                       
                                                 // update char_count.                       
                                                 // if character is not found in                       
                                                 // char_count then increase count                       
                                                 for                                     (                                     int                                     i = 0; i < s2.Length; i++)                       
                                                 char_count[s2[i] -                                     'a'                                     ]--;                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < 26; ++i)                       
                                                 {                       
                                                 if                                     (char_count[i] != 0)                       
                                                 {                       
                                                 count+= Math.Abs(char_count[i]);                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     count / 2;                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
           
                                                 string                                     s1 =                                     "ddcf"                                     ;                       
                                                 string                                     s2 =                                     "cedk"                                     ;                       
                                   
                                                 Console.WriteLine(                       
                                                 countManipulations(s1, s2));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP Program to find minimum number                       
                         // of manipulations required to make                       
                         // two strings identical                       
           
                         // Counts the no of manipulations                       
                         // required                       
                         function                                     countManipulations(                                     $s1                                     ,                                     $s2                                     )                       
                         {                       
                                                 $count                                     = 0;                       
           
                                                 // store the count of character                       
                                                 $char_count                                     =                                     array_fill                                     (0, 26, 0);                       
           
                                                 // iterate though the first String                       
                                                 // and update count                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     strlen                                     (                                     $s1                                     );                                     $i                                     ++)                       
                                                 $char_count                                     [ord(                                     $s1                                     [                                     $i                                     ]) -                       
                                                 ord(                                     'a'                                     )] += 1;                       
           
                                                 // iterate through the second string                       
                                                 // update char_count.                       
                                                 // if character is not found in                       
                                                 // char_count then increase count                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     strlen                                     (                                     $s2                                     );                                     $i                                     ++)                       
                                                 {                       
                                                 $char_count                                     [ord(                                     $s2                                     [                                     $i                                     ]) -                       
                                                 ord(                                     'a'                                     )] -= 1;                       
                                   
                                                 }                       
                                   
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     < 26;                                     $i                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $char_count                                     [i]!=0)                       
                                                 {                       
                                                 $count                                     +=                                     abs                                     (                                     $char_count                                     [i]);                       
                                                 }                       
                                                 }                       
                                                 return                                     (                                     $count                                     ) / 2;                       
                         }                       
           
                         // Driver code                       
                         $s1                                     =                                     "ddcf"                                     ;                       
                         $s2                                     =                                     "cedk"                                     ;                       
           
                         echo                                     countManipulations(                                     $s1                                     ,                                     $s2                                     );                       
           
                         // This code is contributed by Ryuga                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find minimum number                       
                         // of manipulations required to make                       
                         // two strings identical                       
                                   
                         // Counts the no of manipulations                       
                         // required                       
                         function                                     countManipulations(s1, s2)                       
                         {                       
                                                 let count = 0;                       
           
                                                 // Store the count of character                       
                                                 let char_count =                                     new                                     Array(26);                       
                                                 for                                     (let i = 0; i < char_count.length; i++)                       
                                                 {                       
                                                 char_count[i] = 0;                       
                                                 }                       
                                   
                                                 // Iterate though the first String and                       
                                                 // update count                       
                                                 for                                     (let i = 0; i < s1.length; i++)                       
                                                 char_count[s1[i].charCodeAt(0) -                       
                                                 'a'                                     .charCodeAt(0)]++;                       
           
                                                 // Iterate through the second string                       
                                                 // update char_count.                       
                                                 // If character is not found in char_count                       
                                                 // then increase count                       
                                                 for                                     (let i = 0; i < s2.length; i++)                       
                                                 {                       
                                                 char_count[s2[i].charCodeAt(0) -                       
                                                 'a'                                     .charCodeAt(0)]--;                       
                                                 }                       
                                   
                                                 for                                     (let i = 0; i < 26; ++i)                       
                                                 {                       
                                                 if                                     (char_count[i] != 0)                       
                                                 {                       
                                                 count += Math.abs(char_count[i]);                       
                                                 }                       
                                                 }                       
                                                 return                                     count / 2;                       
                         }                       
           
                         // Driver code                       
                         let s1 =                                     "ddcf"                                     ;                       
                         let s2 =                                     "cedk"                                     ;                       
           
                         document.write(countManipulations(s1, s2));                       
           
                         // This code is contributed by avanitrachhadiya2155                       
                                   
                         </script>                       

输出：

时间复杂度：O（n） 哪里 N 是字符串的长度。

本文由 苏米特·戈什 并通过 伊斯塔哈·安萨里医学博士 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章