将字符串转换为回文的最低成本-yiteyi-C++库

将字符串S转换为回文字符串。只能用任何其他字符替换一个字符。用任何其他字符替换字符“a”时，成本为1个单位，同样地，“b”的成本为2个单位…。。对于“z”，它是26个单位。找到将字符串S转换为回文字符串所需的最低成本。 例如：

null

Input : abcdefOutput : 6Explanation: replace 'a', 'b' and 'c' => cost= 1 + 2 + 3 = 6 Input : abaOutput : 0

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

这个想法是从字符串的两端开始比较。允许我初始化为0索引，然后 J 初始化为长度–1。如果两个索引中的字符不相同，则会产生费用。要使成本最低，请替换较小的字符。然后增加我按1递减 J 到1点。迭代到我少于 J .

C++

                         // CPP program to find minimum cost to make                       
                         // a palindrome.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to return cost                       
                         int                                     cost(string str)                       
                         {                       
                                                 // length of string                       
                                                 int                                     len = str.length();                       
                                   
                                                 // Iterate from  both sides of string.                       
                                                 // If not equal, a cost will be there                       
                                                 int                                     res = 0;                       
                                                 for                                     (                                     int                                     i=0, j=len-1; i < j; i++, j--)                       
                                                 if                                     (str[i] != str[j])                       
                                                 res += min(str[i], str[j]) -                                     'a'                                     + 1;                       
                                   
                                                 return                                     res;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 string str =                                     "abcdef"                                     ;                       
                                                 cout << cost(str) << endl;                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find minimum cost to make                       
                         // a palindrome.                       
                         import                                     java.io.*;                       
           
                         class                                     GFG                       
                         {                       
                                                 // Function to return cost                       
                                                 static                                     int                                     cost(String str)                       
                                                 {                       
                                                 // length of string                       
                                                 int                                     len = str.length();                       
                                   
                                                 // Iterate from both sides of string.                       
                                                 // If not equal, a cost will be there                       
                                                 int                                     res =                                     0                                     ;                       
                                                 for                                     (                                     int                                     i =                                     0                                     , j = len -                                     1                                     ; i < j; i++, j--)                       
                                                 if                                     (str.charAt(i) != str.charAt(j))                       
                                                 res += Math.min(str.charAt(i), str.charAt(j))                       
                                                 -                                     'a'                                     +                                     1                                     ;                       
                                   
                                                 return                                     res;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 String str =                                     "abcdef"                                     ;                       
                                                 System.out.println(cost(str));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

Python3

                         # python program to find minimum                       
                         # cost to make a palindrome.                       
           
                         # Function to return cost                       
                         def                                     cost(st):                       
                                   
                                                 # length of string                       
                                                 l                                     =                                     len                                     (st)                       
                                   
                                                 # Iterate from both sides                       
                                                 # of string. If not equal,                       
                                                 # a cost will be there                       
                                                 res                                     =                                     0                       
                                                 j                                     =                                     l                                     -                                     1                       
                                                 i                                     =                                     0                       
                                                 while                                     (i < j):                       
                                                 if                                     (st[i] !                                     =                                     st[j]):                       
                                                 res                                     +                                     =                                     (                                     min                                     (                                     ord                                     (st[i]),                       
                                                 ord                                     (st[j]))                                     -                       
                                                 ord                                     (                                     'a'                                     )                                     +                                     1                                     )                       
                                   
                                                 i                                     =                                     i                                     +                                     1                       
                                                 j                                     =                                     j                                     -                                     1                       
                                   
                                                 return                                     res                       
           
                         # Driver code                       
                         st                                     =                                     "abcdef"                                     ;                       
                         print                                     (cost(st))                       
           
                         # This code is contributed by                       
                         # Sam007                       

C#

                         // C# program to find minimum cost                       
                         // to make a palindrome.                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                                   
                                                 // Function to return cost                       
                                                 static                                     int                                     cost(String str)                       
                                                 {                       
                                                 // length of string                       
                                                 int                                     len = str.Length;                       
                                   
                                                 // Iterate from both sides of string.                       
                                                 // If not equal, a cost will be there                       
                                                 int                                     res = 0;                       
                                                 for                                     (                                     int                                     i = 0, j = len - 1; i < j; i++, j--)                       
                                                 if                                     (str[i] != str[j])                       
                                                 res += Math.Min(str[i], str[j])                       
                                                 -                                     'a'                                     + 1;                       
                                   
                                                 return                                     res;                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 string                                     str =                                     "abcdef"                                     ;                       
                                                 Console.WriteLine(cost(str));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by vt_m.                       

PHP

                         <?php                       
                         // PHP program to find minimum                       
                         // cost to make a palindrome.                       
           
                         // Function to return cost                       
                         function                                     cost(                                     $str                                     )                       
                         {                       
                                                 // length of string                       
                                                 $len                                     =                                     strlen                                     (                                     $str                                     );                       
                                   
                                                 // Iterate from both sides                       
                                                 // of string. If not equal,                       
                                                 // a cost will be there                       
                                                 $res                                     = 0;                       
                                                 for                                     (                                     $i                                     = 0,                                     $j                                     =                                     $len                                     - 1;                       
                                                 $i                                     <                                     $j                                     ;                                     $i                                     ++,                                     $j                                     --)                       
                                                 if                                     (                                     $str                                     [                                     $i                                     ] !=                                     $str                                     [                                     $j                                     ])                       
                                                 $res                                     += (min(ord(                                     $str                                     [                                     $i                                     ]),                       
                                                 ord(                                     $str                                     [                                     $j                                     ])) -                       
                                                 ord(                                     'a'                                     ) + 1 );                       
                                   
                                                 return                                     $res                                     ;                       
                         }                       
           
                         // Driver code                       
                         $str                                     =                                     "abcdef"                                     ;                       
                         echo                                     cost(                                     $str                                     );                       
           
                         // This code is contributed by Sam007                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript program to find minimum cost                       
                                                 // to make a palindrome.                       
                                   
                                                 // Function to return cost                       
                                                 function                                     cost(str)                       
                                                 {                       
                                                 // length of string                       
                                                 let len = str.length;                       
                                   
                                                 // Iterate from both sides of string.                       
                                                 // If not equal, a cost will be there                       
                                                 let res = 0;                       
                                                 for                                     (let i = 0, j = len - 1; i < j; i++, j--)                       
                                                 {                       
                                                 if                                     (str[i] != str[j])                       
                                                 {                       
                                                 res += Math.min(str[i].charCodeAt(), str[j].charCodeAt()) -                                     'a'                                     .charCodeAt() + 1;                       
                                                 }                       
                                                 }                       
                                   
                                                 return                                     res;                       
                                                 }                       
                                   
                                                 let str =                                     "abcdef"                                     ;                       
                                                 document.write(cost(str));                       
                                   
                         </script>                       

输出：

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

THE END

技术文章